Phoenicopterus novaehollandiae was named based on a single tarsometatarsus that retains a nearly complete distal end and approximately 95% of the shaft. The bone was discovered in a layer of mudstone that is part of the Etadunna Formation, southeast of Lake Pitikanta within the Lake Eyre basin.^[1]

The general anatomy of the holotype tarsometatarsus resembles that of the modern greater flamingo and American flamingo. Being slender and elongated. P. novaehollandiae however differs significantly in the fact that there is a clear scar on the bone from where the first metatarsus, the first toe, would connect to the tarsometatarsus. In modern Phoenicopterus species, the hallux is heavily reduced and only weakly connected to the leg by ligaments. In other modern flamingo genera, namely Phoenicoparrus (Jame's & Andean flamingo) and Phoeniconaias (lesser flamingo), this toe is even shorter or entirely absent. This suggests that, while not preserved itself, the first toe of P. novaehollandiae would be longer and more functional than in any modern flamingo. The third and fourth trochlea are closer together than in modern species and the second trochlea is narrower. These features might indicate that the toes weren't as spread apart, but likely had little impact on the foot's function. In size the holotype falls within the range expected from the greater flamingo, but is located towards the upper maximum, suggesting that it was among the larger species within the Phoenicopterus genus.^[1]

Phoenicopterus novaehollandiae likely behaved and foraged much like modern flamingos, being a stilt-legged wading bird according to Miller. The presence of flamingos in the Neogene of Australia in the form of P. novaehollandiae and Phoeniconotius eyrensis indicates that long-lasting, shallow freshwater lakes must have been present in central Australia at the time to sustain the colonies these birds typically live in. As fossil flamingos are found in Australia up to the Pleistocene, Miller argues that the increased aridification of the continent eventually lead to the extinction of flamingos in Australia, as shallow lakes still found are typically not permanent and thus incapable of sustaining flamingos feeding, nesting and raising their young.^[1]