Surface translocation by the soil bacterium Myxococcus xanthus is a complex multicellular phenomenon that entails two motility systems. However, the mechanisms by which the activities of individual cells are coordinated to manifest this collective behaviour are currently unclear. Here we have developed a novel assay that enables detailed microscopic examination of M. xanthus motility at the interstitial interface between solidified nutrient medium and a glass coverslip. Under these conditions, M. xanthus motility is characterised by extensive micro-morphological patterning that is considerably more elaborate than occurs at an air-surface interface. We have found that during motility on solidified nutrient medium, M. xanthus forges an interconnected furrow network that is lined with an extracellular matrix comprised of exopolysaccharides, extracellular lipids, membrane vesicles and an unidentified slime. Our observations have revealed that M. xanthus motility on solidified nutrient medium is a stigmergic phenomenon in which multi-cellular collective behaviours are co-ordinated through trail-following that is guided by physical furrows and extracellular matrix materials.