Three species of Pycnodus, a genus of extinct holostean fishes, have been identified from the Paleocene of Jabal Umm Himar, Harrat Hadan area, south-central Saudi Arabia, an area that was contiguous with Africa during the Early Tertiary. One of the species is larger than any species identified from the Early Tertiary of Africa. Its lower teeth are from 60 to 100 percent wider and 50 percent longer than those in P. mokattamensis, hitherto the largest species known from Africa. The second species, the most poorly represented of the three, is in dental size roughly 40 percent as large as the first species or about the same size as P. variabilis of Africa. The third species is small and, although the position of its teeth cannot be determined, this species clearly is distinct from the two other pycnodonts from Jabal Umm Himar.