A partial skeleton of a plesiosaur (Reptilia: Sauropterygia) from the Hiccles Cove Formation (Middle Jurassic: Callovian) of Melville Island, Canadian Arctic Archipelago, is the first marine reptile fossil with well-preserved skull from the Canadian Arctic and represents a new genus and species of Rhomaleosauridae (Borealonectes russelli). The Rhomaleosauridae are a problematic group, and a review of the current status of included taxa is given prior to the description of the Canadian material. The holotype and only known specimen of the new species consists of the skull, anterior cervicals, and right forelimb. The new taxon is characterized by the large prefrontal and the configuration of the postorbital bar in which the postfrontal is excluded from the supratemporal fenestra; these are potentially unique features among rhomaleosaurids. It exhibits a combination of primitive and derived characteristics that are variable among rhomaleosaurids, such as the absence of the dorsomedian foramen and anterior pterygoid vacuity on the palate, and the presence of straight shaft of humerus. The occurrence of this specimen suggests a global distribution of rhomaleosaurids, and it is also significant as one of the few Jurassic plesiosaurs known from North America.