The genus is known from the type species Stahleckeria potens, which was first collected from the Ladinian-age Santa Maria Formation in the Paleorrota fossil site of Brazil.

Stahleckeria was named in honor of Rudolf Stahlecker, who discovered the first specimens during a 1935 expedition led by paleontologist Friedrich von Huene to the Chiniquá fossil site.

In addition to the remains of Stahleckeria potens, fossils of the cynodont Chiniquodon and an unidentified rauisuchian have also been found in the Omingonde deposits.

The presence of these animals in South America and in Africa at the same time is strong evidence that the two continents were once one uninterrupted landmass with a uniform climate and habitat that land animals such as Stahleckeria could travel freely between.

[3] The fossils of Stahleckeria potens discovered in Brazil are currently in Germany in the museum of the University of Tübingen.