|Fibula of the holotype.|
The type species, V. guerichi, was first described by Huene in 1932 as a coelurosaur, based on the proximal portion of a very poorly preserved fibula that was discovered in the Lissauer Breccia of southern Poland by Georg Gürich around 1898. The bone was damaged during the Second World War and was thought to have been destroyed until it was rediscovered in 2012. In 1956, von Huene placed Velocipes in the Halticosauridae, which has since become monotypic to only include Halticosaurus. In 1984, Samuel Paul Welles considered Velocipes to be synonymous with Liliensternus.
A later paper, published in 2000 by Rauhut and Hungerbuhler, claimed that the only specimen of this animal was not well preserved enough to be confidently identified as part of a fibula, and classified the genus as an "indeterminate vertebrate". In 2004, Ronald Tykoski and Timothy Rowe listed Velocipes as a possible ceratosaur or coelophysoid. Weishampel et al. (2004) also listed Velocipes as a possible ceratosaur.
However, an SVP abstract reviewing putative dinosauriform remains from the Triassic of southern Poland confirmed the original theropod classification of Velocipes by von Huene, which was elaborated in detail in a 2016 paper. The authors considered Velocipes to have been a basal theropod or a neotheropod.