The most common fossils of C. megalodon are its teeth. The diagnostic characters of C. megalodon teeth include: triangular shape, robust structure, large size, fine serrations, and visible v-shaped neck. The teeth of C. megalodon can measure over 180 millimetres (7.1 in) in slant height or diagonal length, and are the largest in size of any known shark species.

Fossil vertebrae of C. megalodon have also been occasionally found. The most notable example is a partially preserved but associated vertebral column of a single C. megalodon specimen, which was excavated from Antwerp basin, Belgium by M. Leriche in 1926. This specimen comprises 150 vertebral centra, with the largest centra being 155 mm in diameter. However, scientists have claimed that considerably larger vertebral centra can be expected from C. megalodon. Interestingly, a partially preserved but associated vertebral column of another C. megalodon specimen was excavated from Gram clay, Denmark by Bendix-Almgeen in 1983. This specimen comprises 20 vertebral centra, with the largest centra being around 230 mm in diameter.

Among extant species, the great white shark is regarded as the best analogue to C. megalodon. The lack of well preserved fossil skeletons of C. megalodon have forced scientists to rely on the morphology of the great white shark for the basis of its reconstruction and size estimation.