The high speed would have been necessary to escape larger theropods; Bonaparte suggested that Velocisaurus was itself an omnivore, as indicated by the fact that the sole claw found, of the fourth toe, was not trenchant but relatively straight.

The generic name is derived from Latin velox, "swift", a reference to the fact that the hind leg and foot show adaptations for running.

The genus and species are based on the holotype MUCPv 41, a nearly complete right leg which is part of the collection of the Museo de la Universidad Nacional del Comahue.

A study of theropod relationships by Fernando Novas and Sebastian Apesteguia in 2003 showed that Velocisaurus was a close relative of the strange ceratosaur Masiakasaurus.

[5] In a 2001 study conducted by Bruce Rothschild and other paleontologists, 12 foot bones referred to Velocisaurus were examined for signs of stress fracture, but none were found.