Labidiosuchus is known only from the holotype specimen DGM 1480-R, an incomplete lower jaw with the anterior part of the dentary complete, lacking most of the right mandibular ramus and the end of the left mandibular ramus. It is housed at the Earth Science Museum of the Departamento Nacional da Produção Mineral. A cast is housed at the Departamento de Geologia, Universidade Federal do Rio de Janeiro. It was found in Serra do Veadinho site, Municipality of Peirópolis of Minas Gerais State, from a site in which Itasuchus, yet another enigmatic mesoeucrocodylian, was found. It was collected from the Serra da Galga Member of the Marília Formation (Bauru Group) in the Bauru Basin, which dates to the late Maastrichtian stage of the Late Cretaceous.
Labidiosuchus is characterized by a unique combination of characters, including four autapomorphies (unique characteristics) such as the presence of small teeth on the medial side of the anterior portion of the dentary. Labidiosuchus had a proportionally large number of the teeth (at least eight on each side of the jaw), packed tightly, some located lateral to each other. The first pair of teeth is procumbent and larger than all others. Its mandible is strongly anterodorsally projected and there is a symphyseal platform that holds the teeth. Due to the incompleteness of the holotype, its feeding preferences or the exact phylogenetic position can't be determined with certainty. DGM 1480-R was briefly described by Campos & Azevedo (1992) as a dinosaur lower jaw. The preserved specimen has a length of about 70.5 mm (2.78 in) and suggests that the jaw had a Y-shaped outline in dorsal view. This condition of the lower jaw is shared with many ziphosuchians, such as Adamantinasuchus, Sphagesaurus, Notosuchidae and probably with Candidodon. Other characteristics of the dentition are shared with many members of the Sphagesauridae (such as the strong protruding forward inclination of the first pair of teeth and the presence of anterior projection on the lower jaw). This allows to allocate it with the Notosuchia, a large group of crocodylomorphs that shows a great variation of dentition.