The Asian Ostrich became extinct after the end of the last iceage, and images of ostriches have been found in China on petroglyphs and prehistoric pottery, indicating that the ostriches were still around at the time of the early humans of ancient China.
The Chinese Phoenix, or Fenghuang, (凤凰) was said to be made up of the beak of a rooster, the face of a swallow, the forehead of a fowl, the neck of a snake, the breast of a goose, the back of a tortoise, the hindquarters of a stag and the tail of a fish.
This combination of features could also be describing an ostrich - the long neck of a snake, the fat breast of a goose, the dark shell-shaped back of the tortoise, and the huge hindquarters of a stag. Common depictions of the Phoenix also show it destroying snakes with wings spread. Ostriches eat snakes, and do spread their wings during courtship or aggression.
It is known that the range of the Ostrich did extend from North Africa, across the Middle East and into Central Asia. The Middle Eastern Ostrich only became extinct as recently as 1966, and was probably as close as we could get to imagining what the Asian ostrich looked like to the ancient Chinese, and maybe what the image of the Phoenix was originally based on.
