Signal peptides are a cornerstone mechanism for cellular protein localization, yet until now experimental determination of signal peptides has come from only a narrow taxonomic sampling. As a result, the dominant view is that Sec-cleaved signal peptides in prokaryotes are defined by a canonical AxA motif. Although other residues are permitted in the motif, alanine is by far the most common. Here we broadly examine proteomics data to reveal the signal peptide sequences for 32 bacterial and archaeal organisms from nine phyla and demonstrate that this alanine preference is not universal. Discoveries include fundamentally distinct signal peptide motifs from Alphaproteobacteria, Spirochaetes, Thermotogae and Euryarchaeota. In these novel motifs, alanine is no longer the dominant residue but has been replaced in a different way for each taxon. Surprisingly, divergent motifs correlate with a proteome-wide reduction in alanine. Computational analyses of ~1,500 genomes reveal numerous major evolutionary clades which have replaced the canonical signal peptide sequence with novel motifs.