The FP (Fbxo7/PI31) domains found in the F-box protein Fbxo7 and the proteasome inhibitor PI31 mediate the homodimerization and heterodimerization of Fbxo7 and PI31. Fbxo7 is the substrate-recognition subunit of the SCFFbxo7 (Skp1-Cul1-F-box protein) E3 ubiquitin ligase that catalyzes the ubiquitination of hepatoma up-regulated protein (HURP) and inhibitor of apoptosis protein (IAP). Fbxo7 also interacts with proteins that are not substrates of the ubiquitin proteasome system, such as Cdk6 and PI31. Here, the crystal structure of the Fbxo7 FP domain is reported at 2.0 Å resolution. The Fbxo7 FP domain adopts an α/β-fold similar to that of the PI31 FP domain. However, an α-helix and three β-strands in the Fbxo7 FP domain are longer than their counterparts in the PI31 FP domain. The differences in these secondary-structural elements are spatially clustered to define a more structured and extended C-terminal end of the Fbxo7 FP domain. The two FP domains also differ substantially in the length and conformation of the longest connecting loop. More importantly, structural differences between the two FP domains lead to drastically different modes of inter-domain protein–protein interaction. The inter-domain interface of the Fbxo7 FP domain is defined by the α-helical surface in one protomer and the β-sheet surface in the other protomer, whereas for the PI31 domain it is defined by either the α-helical surfaces or the β-sheet surfaces in both protomers. The inter-domain interaction of the Fbxo7 FP domain is much more extensive, featuring a larger contact surface area, better shape complementarity and more hydrophobic and hydrogen-bonding interactions. The Fbxo7 FP domain also has the potential to bind two protein partners simultaneously using the α-helical and β-sheet surfaces. The results of this structural study provide critical insights into how Fbxo7 may dimerize (or multimerize) and interact with other regulatory proteins via the FP domain.