Mystriosuchus westphali is based on a large, well-preserved cranium and a snout fragment from the Stubensandstein (Norian) of south-west Germany. The hypodigm is redescribed and new or poorly known cranial structures in phytosaurs are discussed. For the first time, the presence of a premaxillary crest is substantiated in a phytosaur. The type specimen shows a supernumerary occipital element (='tabular') that is probably fused to the parietal in other phytosaurs, and an orbitosphenoid. A computerised parsimony analysis confirms the hypothesis that Mystriosuchus is nested within Pseudopalatinae, the most derived clade of phytosaurs, and thus does not fall within basal phytosaurs. Mystriosuchus is characterised by five unique features (slit-like interpremaxillary fossa, triangular cross-section of the postorbito-squamosal bar, strongly reduced posttemporal fenestra, and two features of the cranial sculpture), plus eight synapomorphies that also occur in some more distantly related taxa. Mystriosuchus westphali is diagnosed by, among other apomorphies, a distinct premaxillary crest, a squamosal-prooutic contact, absence of a posterior process of the squamosal, and a slit-like posttemporal fenestra. The type species Mystriosuchus planirostris shows, most significantly, the naris facing forward anteriorly and upward posteriorly, and the longest rostrum and the highest degree of depression of the supratemporal opening in any phytosaur. Mystriosuchus exemplifies a common pattern in phytosaurids in being a genus that includes a gracile, elongated, slender-snouted and a more robust species with a broader, often crested snout. This study demonstrates that a detailed analysis of the cranial anatomy and the rigorous application of cladistic principles to identified character states help to clarify current inconsistencies in the taxonomy and nomenclature of phytosaurs.