The proteins of the Mxd family (formally known as Mad) are antagonists of the oncoprotein c-Myc. They compete with c-Myc for their obligate partner Max to prevent the c-Myc/Max heterodimer from binding to E-box sequences in the target gene promoters. In cancer cells, where Myc is overexpressed, the expression of Mxd proteins is usually insufficient or abrogated. However, the reintroduction of Mxd1 expression in these cells prevents growth and proliferation. While the antagonism of c-Myc functions by Mxd proteins is of potential relevance for the development of cancer treatment strategies, the structural determinants responsible for the specific heterodimerization between the Mxd and the Max b-helix-loop-helix-leucine zippers are not fully understood. Moreover, whether the heterodimer is assembled on DNA or in the nucleoplasm prior to DNA binding is under debate. In this article, we demonstrate that Mxd1 D112a and Max N78a and H81d, which are located in the leucine zippers of the proteins, can dictate the specificity of heterodimerization and whether or not the Mxd1/Max/DNA complex forms. Our results also indicate that additional specific determinants exist in the helix-loop-helix domains of Max and Mxd1. Finally, we provide evidence that heterodimerization must precede DNA binding in vivo.