Gar is an actinopterygian that has bone, dentin, enameloid, and ganoin (enamel) in teeth and/or scales. Mineralization of these tissues involves genes encoding various secretory calcium-binding phosphoproteins (SCPPs) in osteichthyans, but no SCPP genes have been identified in chondrichthyans to date. In the gar genome, we identified 38 SCPP genes, seven of which encode “acidic-residue-rich” proteins and 31 encode “Pro/Gln (P/Q) rich” proteins. These gar SCPP genes constitute the largest known repertoire, including many newly identified P/Q-rich genes expressed in teeth and/or scales. Among gar SCPP genes, six acidic and three P/Q-rich genes were identified as orthologs of sarcopterygian genes. The sarcopterygian orthologs of most of these acidic genes are involved in bone and/or dentin formation, and sarcopterygian orthologs of all three P/Q-rich genes participate in enamel formation. The finding of these genes in gar suggests that an elaborate SCPP gene-based genetic system for tissue mineralization was already present in stem osteichthyans. While SCPP genes have been thought to originate from ancient SPARCL1, SPARCL1L1 appears to be more closely related to these genes, because it established a structure similar to acidic SCPP genes probably in stem gnathostomes, perhaps at about the same time with the origin of tissue mineralization. Assuming enamel evolved in stem osteichthyans, all P/Q-rich SCPP genes likely arose within the osteichthyan lineage. Furthermore, the absence of acidic SCPP genes in chondrichthyans might be explained by the secondary loss of earliest acidic genes. It appears that many SCPP genes expanded rapidly in stem osteichthyans and in basal actinopterygians.