Inteins are naturally occurring intervening sequences that catalyze a protein splicing reaction resulting in intein excision and concatenation of the flanking polypeptides (exteins) with a native peptide bond. Inteins display a diversity of catalytic mechanisms within a highly conserved fold that is shared with hedgehog autoprocessing proteins. The unusual chemistry of inteins has afforded powerful biotechnology tools for controlling enzyme function upon splicing and allowing peptides of different origins to be coupled in a specific, time-defined manner. The extein sequences immediately flanking the intein affect splicing and can be defined as the intein substrate. Because of the enormous potential complexity of all possible flanking sequences, studying intein substrate specificity has been difficult. Therefore, we developed a genetic selection for splicing-dependent kanamycin resistance with no significant bias when six amino acids that immediately flanked the intein insertion site were randomized. We applied this selection to examine the sequence space of residues flanking the Nostoc punctiforme Npu DnaE intein and found that this intein efficiently splices a much wider range of sequences than previously thought, with little N-extein specificity and only two important C-extein positions. The novel selected extein sequences were sufficient to promote splicing in three unrelated proteins, confirming the generalizable nature of the specificity data and defining new potential insertion sites for any target. Kinetic analysis showed splicing rates with the selected exteins that were as fast or faster than the native extein, refuting past assumptions that the naturally selected flanking extein sequences are optimal for splicing.