Mammals are the only surviving group of Cynodontia, a synapsid clade that first appeared in the fossil record in the late Permian, ~260 million years ago. Using three metrics that capture skeletal completeness, we quantify the quality of the early cynodont fossil record in time and space to evaluate the impact of sampling and preservational biases on our understanding of the group's evolutionary history. There is no consistent global sampling signal for early cynodonts. Completeness of the cynodont fossil record increases across the Permian???Triassic boundary, peaking in the Early to early Late Triassic. This peak is dominated by specimens from southern Africa and South America, where a highly seasonal climate probably favoured preservation. Completeness is generally lower thereafter, correlating with a shift from a Gondwanan to a predominantly Laurasian fossil record. Phylogenetic and stratigraphic congruence in early cynodonts is high, although their fossil record exhibits less skeletal completeness overall than other tetrapod clades, including the contemporaneous anomodont synapsids. This discrepancy could be due to differences in the diagnosability of their fossils, especially for small???bodied species. Establishing the timing and assembly of derived (???mammalian???) anatomical features in Cynodontia is obscured by sampling. Two of the major nodes at which acquisition of mammalian features is concentrated (Cynodontia and Mammaliamorpha) suffer from lengthy intervals of poor sampling before becoming abundant parts of tetrapod faunas. Low completeness in these intervals limits our ability to determine when certain ???key??? mammalian characteristics evolved, or to identify the selective pressures that might have driven their origins.