In vertebrates, bone and dentin have been found in the earliest mineralized skeletal elements, which consisted of odontodes and osseous plates. For more than 450 million years, the two tissues evolved concomitantly in various skeletal elements, which were either conserved or subjected to wide changes as illustrated in extinct and extant lineages: odontodes, teeth, scales, osteoderms, fin rays, bony spines, dermal bones, and cartilage bones from the endoskeleton. Bone is cellular in most species, with a few exceptions of bone lacking osteocytes in some early vertebrates and in derived teleost fishes. Dentin has been classified into eight distinct types and some of them are highly specialized such as the elasmodin of fish scales. In this chapter, we summarize our knowledge and propose a scenario for the evolution of these two tissues. We also review hypotheses proposed for tracing back the origin of the skeletal tissues during the prechordate-vertebrate transition. Specific molecules and specialized cells were undoubtedly differentiated prior to the identification of these tissues in the fossil record. Cartilage, bone and dentin matrices were probably created when typical fibrillar collagen type II and type I, the major components of these skeletal tissues, were recruited after the genome duplications that predated the vertebrate differentiation. The secretory calcium-binding phosphoproteins (SCPPs) are crucial molecules controling crystallization of calcium phosphate in these skeletal tissues. SCPP genes are thought to have arisen from SPARCL1 (SPARC-like 1), which originated from SPARC (secreted protein, acidic, cystein-rich), at about the same period when fibrillar collagen genes used for vertebrate skeletal tissues were differentiated. Eventually, neural crest-derived specialized cells employed a fibrillar collagen and an SCPP, among other proteins, and created the first mineralized dermal skeletal elements, probably in association with sensory organs located on the body surface. Currently at least five acidic SCPPs (DSPP, DMP1, IBSP, MEPE, SPP1) are involved in the mineralization of bone and dentin tissues in mammals, and other SCPPs were identified in teleost fishes. In this chapter we analyze the evolution of these SCPPs and their relationships within the framework of vertebrate phylogeny.