Multi-legged robots are effective at traversing rough terrain. However, terrains that include collapsible footholds (i.e. regions that can collapse when stepped on) remain a significant challenge, especially since such situations can be extremely difficult to anticipate using only exteroceptive sensing. State-of-the-art methods typically use various stabilisation techniques to regain balance and counter changing footholds. However, these methods are likely to fail if safe footholds are sparse and spread out or if the robot does not respond quickly enough after a foothold collapse. This paper presents a novel method for multi-legged robots to probe and test the terrain for collapses using its legs while walking. The proposed method improves on existing terrain probing approaches, and integrates the probing action into a walking cycle. A follow-the-leader strategy with a suitable gait and stance is presented and implemented on a hexapod robot. The proposed method is experimentally validated, demonstrating the robot can safely traverse terrain containing collapsible footholds.