Rukwasuchus is known from its holotype, RRBP 08630, a well-preserved rear part of the skull including the cranial table, braincase, and interorbital region lacking the rostrum, the front portion of the palate, both lacrimals, jugals, and quadratojugals, as well as the mandible. RRBP 08630 was collected during 2008 at Namba 2 locality (also known as RRBP 2007-02), together with the titanosaurian Rukwatitan bisepultus which is exclusive to this locality. Material referred to Rukwasuchus includes four isolated teeth, which came from the neighboring localities RRBP 2007-01 yielding the 3 teeth RRBP 07351, 07369, 09362, and RRBP 2009-01 yielding the tooth RRBP 09367. All specimens came from approximately 25 km south of Lake Rukwa in the Galula Study Area, Rukwa Rift Basin of southwestern Tanzania, belonging to the Namba Member of the Galula Formation which dates to the late Aptian or possibly early Cenomanian stage of the middle Cretaceous, approximately 100 mya.^[1]

Rukwasuchus was named by Joseph J. W. Sertich and Patrick M. O’Connor in 2014 and the type species is Rukwasuchus yajabalijekundu. The generic name refers to Lake Rukwa and the Rukwa Rift Basin, located in southwestern Tanzania, where the holotype of Rukwasuchus and other vertebrates were collected by the Rukwa Rift Basin Project, and suchus, Latinized from the Greek souchos, an Egyptian crocodile god. The specific name yajabalijekundu is derived from the Swahili language meaning "of/from the red outcrop", in reference to the Red Sandstone Group deposits exposed at the basin.^[1]

The skull of Rukwasuchus possesses several autapomorphies which distinguished it from other crocodyliforms. These include the presence of a mediolaterally narrow, elongate, and septate internal narial fenestra located anteriorly on the pterygoid, the presence of a markedly depressed posterior border of the parietal that excludes the supraoccipital from the dorsal cranial table, and a ventrally directed descending process of the postorbital with a well-developed posteroventral process. The morphology of the skull and isolated teeth suggests close relations to the peirosaurid Hamadasuchus rebouli from the middle Cretaceous Kem Kem Beds of Morocco. Rukwasuchus is the only known sub-Saharan peirosaurid from Africa, thus representing the only link between middle Cretaceous southern vertebrate faunas and much more abundant and taxonomically diverse faunas from northern Africa.^[1]

A phylogenetic analysis of Crocodyliformes supports a close relationship between Rukwasuchus and other African members of Trematochampsidae, e.g. Hamadasuchus and Trematochampsa, that is positioned within a larger clade of Gondwanan peirosaurids. The following cladogram is simplified after the analysis of Sertich & O’Connor (2014); the relationships within Sebecosuchia and advanced notosuchians are not shown.^[1]