Background: MHC class I (MHCI) molecules are the key presenters of peptides generated through the intracellular pathway to CD8-positive T-cells. In fish, MHCI genes were first identified in the early 1990′s, but we still know little about their functional relevance. The expansion and presumed sub-functionalization of cod MHCI and access to many published fish genome sequences provide us with the incentive to undertake a comprehensive study of deduced teleost fish MHCI molecules. Results: We expand the known MHCI lineages in teleosts to five with identification of a new lineage defined as P. The two lineages U and Z, which both include presumed peptide binding classical/typical molecules besides more derived molecules, are present in all teleosts analyzed. The U lineage displays two modes of evolution, most pronouncedly observed in classical-type alpha 1 domains; cod and stickleback have expanded on one of at least eight ancient alpha 1 domain lineages as opposed to many other teleosts that preserved a number of these ancient lineages. The Z lineage comes in a typical format present in all analyzed ray-finned fish species as well as lungfish. The typical Z format displays an unprecedented conservation of almost all 37 residues predicted to make up the peptide binding groove. However, also co-existing atypical Z sub-lineage molecules, which lost the presumed peptide binding motif, are found in some fish like carps and cavefish. The remaining three lineages, L, S and P, are not predicted to bind peptides and are lost in some species. Conclusions: Much like tetrapods, teleosts have polymorphic classical peptide binding MHCI molecules, a number of classical-similar non-classical MHCI molecules, and some members of more diverged MHCI lineages. Different from tetrapods, however, is that in some teleosts the classical MHCI polymorphism incorporates multiple ancient MHCI domain lineages. Also different from tetrapods is that teleosts have typical Z molecules, in which the residues that presumably form the peptide binding groove have been almost completely conserved for over 400 million years. The reasons for the uniquely teleost evolution modes of peptide binding MHCI molecules remain an enigma.