Only a single species of stork, the Black-necked Stork Ephippiorhynchus (= Xenorhynchus) asiaticus, occurs in Australia today, and is known from several fossil localities from the Early Pliocene. Two species of smaller fossil storks are also known, one previously named and one described here. The former, found in the Darling Downs, southeastern Queensland, was named Xenorhynchus nanus De Vis, 1888. Some later authors suggested that this species should be transferred to the living genus Ciconia; this decision is confirmed here, the name for this species becoming Ciconia nana. The second species of small stork comes from several Late Oligocene and Early Miocene sites at Riversleigh, northwestern Queensland. This taxon is referred to the genus Ciconia and distinguished as a new species, C. louisebolesae. It constitutes the earliest record of the Ciconiidae from Australia.