Integral beta-barrel proteins are found in the outer membranes of mitochondria, chloroplasts, and Gram-negative bacteria. The machine that assembles these proteins contains an integral membrane protein, called YaeT in Escherichia coli, which has one or more polypeptide transport-associated (POTRA) domains. The crystal structure of a periplasmic fragment of YaeT reveals the POTRA domain fold and suggests a model for how POTRA domains can bind different peptide sequences, as required for a machine that handles numerous beta-barrel protein precursors. Analysis of POTRA domain deletions shows which are essential and provides a view of the spatial organization of this assembly machine.