Classic nuclear export signals (NESs) confer CRM1-dependent nuclear export. Here we present crystal structures of the RanGTP-CRM1 complex alone and bound to the prototypic PKI or HIV-1 Rev NESs. These NESs differ markedly in the spacing of their key hydrophobic (Φ) residues, yet CRM1 recognizes them with the same rigid set of five Φ pockets. The different Φ spacings are compensated for by different conformations of the bound NESs: in the case of PKI, an α-helical conformation, and in the case of Rev, an extended conformation with a critical proline docking into a Φ pocket. NMR analyses of CRM1-bound and CRM1-free PKI NES suggest that CRM1 selects NES conformers that pre-exist in solution. Our data lead to a new structure-based NES consensus, and explain why NESs differ in their affinities for CRM1 and why supraphysiological NESs bind the exportin so tightly.