Two new tetrapod burrow casts from the Naobaogou Formation (Middle or Late Permian) of Nei Mongol, China are described. It marks the first pre-Cenozoic tetrapod burrow from China, and one of the earliest records of tetrapod burrows. Comparison to other Permian and Triassic burrows suggests that these burrows were created by tetrapod slightly smaller than Lystrosaurus. Deduced from the morphology and sizes of two burrows and known tetrapods of the Naobaogou Formation, the burrow should be the production of a therapsid, most likely a dicynodon. These burrows indicate a seasonal climate and this area was semiarid or arid during that time.