The adaptor protein ankyrin-R interacts via its membrane binding domain with the cytoplasmic domain of the anion exchange protein (AE1) and via its spectrin binding domain with the spectrin-based membrane skeleton in human erythrocytes. This set of interactions provides a bridge between the lipid bilayer and the membrane skeleton, thereby stabilizing the membrane. Crystal structures for the dimeric cytoplasmic domain of AE1 (cdb3) and for a 12-ankyrin repeat segment (repeats 13-24) from the membrane binding domain of ankyrin-R (AnkD34) have been reported. However, structural data on how these proteins assemble to form a stable complex have not been reported. In the current studies, site-directed spin labeling, in combination with electron paramagnetic resonance (EPR) and double electron-electron resonance, has been utilized to map the binding interfaces of the two proteins in the complex and to obtain inter-protein distance constraints. These data have been utilized to construct a family of structural models that are consistent with the full range of experimental data. These models indicate that an extensive area on the peripheral domain of cdb3 binds to ankyrin repeats 18-20 on the top loop surface of AnkD34 primarily through hydrophobic interactions. This is a previously uncharacterized surface for binding of cdb3 to AnkD34. Because a second dimer of cdb3 is known to bind to ankyrin repeats 7-12 of the membrane binding domain of ankyrin-R, the current models have significant implications regarding the structural nature of a tetrameric form of AE1 that is hypothesized to be involved in binding to full-length ankyrin-R in the erythrocyte membrane.