The genus was described from a skull discovered in an exposure of the Arcadia Park Shale (lower Middle Turonian) at Cedar Hill, Dallas County in the south-central part of the DFW Metroplex in Texas, United States.

Other fragmentary specimens of Russelosaurus have been recovered from the slightly older Kamp Ranch Limestone at two other localities in the Dallas area.

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.