Bacterial autotransporters comprise a 12-stranded membrane-embedded beta-barrel domain, which must be folded in a process that entraps segments of an N-terminal passenger domain. This first stage of autotransporter folding determines whether subsequent translocation can deliver the N-terminal domain to its functional form on the bacterial cell surface. Here, paired glycine-aromatic 'mortise and tenon' motifs are shown to join neighbouring beta-strands in the C-terminal barrel domain, and mutations within these motifs slow the rate and extent of passenger domain translocation to the surface of bacterial cells. In line with this, biophysical studies of the autotransporter Pet show that the conserved residues significantly quicken completion of the folding reaction and promote stability of the autotransporter barrel domain. Comparative genomics demonstrate conservation of glycine-aromatic residue pairings through evolution as a previously unrecognized feature of all autotransporter proteins.