Assembly of the bacterial flagellum and type III secretion in pathogenic bacteria require cytosolic export chaperones that interact with mobile components to facilitate their secretion. Although their amino acid sequences are not conserved, the structures of several type III secretion chaperones revealed striking similarities between their folds and modes of substrate recognition. Here, we report the first crystallographic structure of a flagellar export chaperone, Aquifex aeolicus FliS. FliS adopts a novel fold that is clearly distinct from those of the type III secretion chaperones, indicating that they do not share a common evolutionary origin. However, the structure of FliS in complex with a fragment of FliC (flagellin) reveals that, like the type III secretion chaperones, flagellar export chaperones bind their target proteins in extended conformation and suggests that this mode of recognition may be widely used in bacteria.