The description of a new species and genus was published in 2019, emerging from research undertaken by Trevor Worthy, Suzanne Hand, Mike Archer, R. Paul Scofield and Vanesa L. De Pietri.

The etymology of the generic epithet Heracles alludes to the earlier naming of a genus, Nelepsittacus, also found in the St Bathan Fauna, which referred to a mythical king Neleus who was slain by the Greek hero Herakles, who also slew all of his sons, save for Nestor.

The authors distinguished the new species with the epithet inexpectatus to describe their astonishment at the unexpected discovery of an enormous parrot-like bird from the Miocene epoch.

The largest known species of Psittaciformes, which comprises the modern parrots and cockatoos, it is estimated to have been around one meter in height, with a body mass of seven kilograms, and presumed to have been flightless, terrestrial and perhaps arboreal.

The fossilised tarsi were deposited in a rich and mixed assemblage of animal remains, including other large species of Aves such as the moa, anatids and an eagle, the bones of which are usually fragmented.

The time of deposition is determined as sixteen to nineteen million years ago, in an area associated with a freshwater lacustrine system, in wet forest dominated by cycad, palm and casuarina species, along with a diverse array of other avian fauna.