The type (and only) specimen of Atrociraptor, holotype RTMP 95.166.1, was discovered by Wayne Marshall in 1995, in layers of the Horseshoe Canyon Formation also containing an Albertosaurus bonebed, near Drumheller. This bonebed is located at the top of Unit 4 of the Horseshoe Canyon Formation, which dates to about 68.5 million years ago. The only known specimen consists of parts of the upper and lower jaws—both premaxillae, a right maxilla, both dentaries—teeth and numerous small fragments. The skull appears to have been unusually short and tall. The teeth are relatively straight, but they emerge from the tooth sockets at an angle to the jaw line, resulting in a strongly raked row of teeth. A number of isolated teeth (previously referred to Saurornitholestes) have also been recovered from the Horseshoe Canyon Formation; they can be recognized by their unusually large serrations.
In 2004 Philip J. Currie and David Varricchio named and described the type species of Atrociraptor: Atrociraptor marshalli. The generic name is derived from the Latin atrox, "savage", and raptor, "seizer". The specific name honours Marshall.
In 2010 Gregory S. Paul estimated its length at two metres, its weight at fifteen kilogrammes. Atrociraptor differs from Bambiraptor and other velociraptorines in its more isodont dentition—the teeth have different sizes but the same form—and short deep snout. A skull opening, the maxillary fenestra, is relatively large and positioned right above another opening, the promaxillary fenestra, a condition not known from other species.
Atrociraptor was by its describers assigned to the Velociraptorinae within a larger Dromaeosauridae. However, in 2009 Currie published a cladistic analysis showing Atrociraptor to be a member of the Saurornitholestinae.