Specific protein-protein interactions play crucial roles in the regulation of any biological process. Recently, a new protein-protein interaction domain termed PB1 (Phox and Bem1) was identified, which is conserved throughout evolution and present in diverse proteins functioning in signal transduction, cell polarity and survival. Here, we investigated the structure and molecular interactions of the PB1 heterodimer complex composed of the PB1 domains of the yeast proteins Bem1 and Cdc24. A structural model of the Cdc24 PB1 was built by homology modeling and molecular dynamics simulations, and experimentally validated by 15N nuclear Overhauser effect spectroscopy (NOESY)-heteronuclear single quantum coherence (HSQC) analysis. Residues at the interface of the complex for both proteins were identified by NMR titration experiments. A model of the heterodimer was obtained by docking of the two PB1 domains with HADDOCK, which applies ambiguous interaction restraints on residues at the interface to drive the docking procedure. The refined model was validated by site-directed mutagenesis on both Bem1 and Cdc24. Finally, the docking was repeated from the newly published NMR structure of Cdc24, allowing us to assess the performance of homology-based docking. Our results provide insight into the molecular structure of the Bem1-Cdc24 PB1-mediated heterodimer, which allowed identification of critical residues at the binding interface.