Bellubrunnus is known from a single complete articulated skeleton, the holotype of the genus, having the accession number BSP–1993–XVIII–2. It was found in the summer of 2002 by an excavation team led by Monika Rothgaenger, the namesake of the species. It was prepared in 2003 by Martin Kapitzke and at first identified as an exemplar of Rhamphorhynchus. It is preserved in ventral view, meaning that the underside of the skeleton can be seen on the limestone slab. The specimen is currently housed in the Bürgermeister-Müller-Museum, although it is cataloged for, and a possession of, the Bayerische Staatssammlung für Paläontologie und historische Geologie. It comes from a quarry at Kohlstatt near the village of Brunn, Upper Palatinate, in a layer of rock that underlies the better-known Solnhofen Limestone. The quarry dates to the late Kimmeridgian stage of the Late Jurassic period, about 151 million years ago. Ultraviolet lighting revealed many details of the fossil but showed no preserved soft tissues.
Bellubrunnus was first described and named by David W. E. Hone, Helmut Tischlinger, Eberhard Frey and Martin Röper in 2012 and the type and only species is Bellubrunnus rothgaengeri. The generic name is derived from the Latin bellus meaning 'beautiful' and brunnus in reference to Brunn, its type locality. The combination then means 'the beautiful one of Brunn'. The specific name, rothgaengeri, honors Monika Rothgaenger for finding the holotype.