Limnoterrestrial tardigrades live and move through complex environments and may face large changes in substrate deformability and surface friction. How organisms control their movements during natural locomotion through uneven or variable terrain is not fully understood; in particular, very little is known about such mechanisms in soft organisms. Despite living in aquatic environments, tardigrades are poor swimmers; they are found primarily on or within the substrate and are among the smallest known walking animals. We analyze the kinematics of freely walking tardigrades (species: Hypsibius dujardini) on substrates of varying stiffness and at different orientations (i.e., on a flat surface and at a 90-degree incline). We find that the stepping pattern of the posterior-most leg pair shows high variability and does not strongly affect walking speed. However, the anterior three leg pairs display, and rarely deviate from, a regular tetrapodal gait analogous to that observed in insects. Despite disparities in size and skeletal and neuronal structure, tardigrades and stick insects both display flat-terrain walking patterns that are well described by the same inter-leg coordination ‘rules’. Further, we find that, in tardigrades, this stepping pattern is robust to changes in both orientation and substrate stiffness. These results have implications for understanding the mechanisms — neural and/or mechanical — underlying coordination during invertebrate locomotion.