The shoebill may have been known to Ancient Egyptians[3] but was not classified until the 19th century, after skins and eventually live specimens were brought to Europe. John Gould very briefly described it in 1850 from the skin of a specimen collected on the upper White Nile by the English traveller Mansfield Parkyns. Gould provided a more detailed description in the following year. He placed the species in its own genus Balaeniceps and coined the binomial name Balaeniceps rex.[4][5][6] The genus name comes from the Latin words balaena "whale", and caput "head", abbreviated to -ceps in compound words.[7] Alternative common names are whalebill,[8] shoe-billed stork and whale-headed stork.[9]

Traditionally considered as allied with the storks (Ciconiiformes), it was retained there in the Sibley-Ahlquist taxonomy which lumped a massive number of unrelated taxa into their "Ciconiiformes". Based on osteological evidence, the suggestion of a pelecaniform affinity was made in 1957 by Patricia Cottam.[10] Microscopic analysis of eggshell structure by Konstantin Mikhailov in 1995 found that the eggshells of shoebills closely resembled those of other Pelecaniformes in having a covering of thick microglobular material over the crystalline shells.[11] In 2003, the shoebill was again suggested as closer to the pelicans (based on anatomical comparisons)[12] or the herons (based on biochemical evidence).[13] A 2008 DNA study reinforces their membership of the Pelecaniformes.[14]

So far, two fossilized relatives of the shoebill have been described: Goliathia from the early Oligocene of Egypt and Paludavis from the Early Miocene of the same country. It has been suggested that the enigmatic African fossil bird Eremopezus was a relative too, but the evidence for that is unconfirmed. All that is known of Eremopezus is that it was a very large, probably flightless bird with a flexible foot, allowing it to handle either vegetation or prey.