The earliest fossil of ostrich-like birds is the Palaeotis living near the Asiatic steppes from the Middle Eocene, a mid-sized flightless bird that was originally believed to be a bustard. Apart from this enigmatic bird, the fossil record of the ostriches continues with several species of the modern genus Struthio which are known from the Early Miocene onwards. While the relationship of the African species is comparatively straightforward, a large number of Asian species of ostrich have been described from fragmentary remains, and their interrelationships and how they relate to the African ostriches are confusing. In China, ostriches are known to have become extinct only around or even after the end of the last ice age; images of ostriches have been found there on prehistoric pottery and petroglyphs.
Several of these fossil forms are ichnotaxa (that is, classified according to the organism’s footprints or other trace rather than its body) and their association with those described from distinctive bones is contentious and in need of revision pending more good material.