The type species, R. coheni, was named for the amateur fossil collector who discovered SMU 73056, and the genus name honours paleontologist Dale A. Russell for his extensive work on mosasaurs ("Russell's lizard"). This is the second species of mosasaur to have been named for Russell, the first being Selmasaurus russelli (Wright and Shannon, 1988). The type specimen of Russellosaurus is notable as being the oldest well-preserved mosasaur yet found in North America.
Polcyn et. Bell (2005, p. 323) diagnose Russellosaurus as follows: "Small, lightly built mosasaur, frontal narrow with a length to width ratio of 1.6:1. Sixteen maxillary teeth and 16 dentary teeth. Anterior premaxilla broad and blunt, in dorsal view the premaxillary-maxillary suture is oblique. The ectopterygoid is lightly built and composed of a distinct small subrectangular pterygoid process and a slender rod-like jugal process. Incipient emargination of the frontal by the external nares. A pair of foramina separated by a thin median septum in the floor of the basioccipital are interpreted as the entrance of the basilar artery, and exit the ventral surface of the basioccipital as multiple small and anteriorly placed foramina. Extreme downgrowth of the pterygoid processes of the basisphenoid. Lightly built postorbitofrontal processes. The pineal foramen is located in the centre of the triangular parietal table. The supraoccipital loose cartilaginous contact with parietal. Median cleft in posterior parietal margin in dorsoventral aspect."
Polcyn et Bell (2005, p. 322) designated Russellosaurus the type genus of a new parafamily of mosasaurs, the Russellosaurina (= subfamily Russellosaurinae of Bell, 1997). This clade of marine lizards is defined as all mosasaurs more closely related to the subfamilies Tylosaurinae and Plioplatecarpinae and their sister group, consisting of the taxa Tethysaurus, Yaguarasaurus, and Russellosaurus, their common ancestor and all descendants than to the subfamily Mosasaurinae. The skull of Russelosaurus shows many characters diagnostic of the Plioplatecarpinae while retaining many plesiomorphic traits. Cladistic analysis indicates a close relationship between Russellosaurus and Yaguarasaurus columbianus, a primitive South American mosasaur from the Turonian of Colombia. Together with Tethysaurus nopcsai, another early mosasauroid from the Turonian of Morocco, these genera are believed to constitute a clade "basal to the divergence" of the subfamilies Plioplatecarpinae and Tylosaurinae.
Based on the lack of fusion between elements of the basicarnium and a high degree of vascularization of the bone surface, which suggests the animal was undergoing a rapid growth stage when it died, the holotype skull of Russellosaurus coheni is believed to have come from a subadult individual. An even more primitive mosasaur, Dallasaurus turneri, was recovered from the same Cedar Hill locality as this specimen.