The oncoprotein MDM2 binds to tumor suppressor protein p53 and inhibits its anticancer activity, which leads to promotion of tumor cell growth and tumor survival. Abrogation of the p53:MDM2 interaction reportedly results in reactivation of the p53 pathway and inhibition of tumor cell proliferation. We recently performed rigorous selection of MDM2-binding peptides by means of mRNA display and identified an optimal 12-mer peptide (PRFWEYWLRLME), named MDM2 Inhibitory Peptide (MIP), which shows higher affinity for MDM2 (and also its homolog, MDMX) and higher tumor cell proliferation suppression activity than known peptides. Here we determined the NMR solution structure of a MIP-MDM2 fusion protein to elucidate the structural basis of the tight binding of MIP to MDM2. A region spanning from Phe3 to Met11 of MIP forms a single α-helix, which is longer than those of the other MDM2-binding peptides. MIP shares a conserved Phe3-Trp7-Leu10 triad, whose side chains are oriented towards and fit into the hydrophobic pockets of MDM2. Additionally, hydrophobic surface patches that surround the hydrophobic pockets of MDM2 are covered by solvent-exposed MIP residues, Trp4, Tyr6, and Met11. Their hydrophobic interactions extend the interface of the two molecules and contribute to the strong binding. The potential MDM2 inhibition activity observed for MIP turned out to originate from its enlarged binding interface. The structural information obtained in the present study provides a road map for the rational design of strong inhibitors of MDM2:p53 binding.