The Type II Secretion System (T2SS) is a molecular machine that drives the secretion of fully-folded protein substrates across the bacterial outer membrane. A key element in the machinery is the secretin: an integral, multimeric outer membrane protein that forms the secretion pore. We show that three distinct forms of T2SSs can be distinguished based on the sequence characteristics of their secretin pores. Detailed comparative analysis of two of these, the Klebsiella-type and Vibrio-type, showed them to be further distinguished by the pilotin that mediates their transport and assembly into the outer membrane. We have determined the crystal structure of the novel pilotin AspS from Vibrio cholerae, demonstrating convergent evolution wherein AspS is functionally equivalent and yet structurally unrelated to the pilotins found in Klebsiella and other bacteria. AspS binds to a specific targeting sequence in the Vibrio-type secretins, enhances the kinetics of secretin assembly, and homologs of AspS are found in all species of Vibrio as well those few strains of Escherichia and Shigella that have acquired a Vibrio-type T2SS.