Inteins are prevalent among extremophiles. Mini-inteins with robust splicing properties are of particular interest for biotechnological applications due to their small size. However, biochemical and structural characterization has still been limited to a small number of inteins, and only a few serve as widely used tools in protein engineering. We determined the crystal structure of a naturally occurring Pol-II mini-intein from Pyrococcus horikoshii and compared all three mini-inteins found in the genome of P. horikoshii. Despite their similar sizes, the comparison revealed distinct differences in the insertions and deletions, implying specific evolutionary pathways from distinct ancestral origins. Our studies suggest that sporadically distributed mini-inteins might be more promising for further protein engineering applications than highly conserved mini-inteins. Structural investigations of additional inteins could guide the shortest path to finding novel robust mini-inteins suitable for various protein engineering purposes.