This paper addresses the problem of evaluating and estimating the mechanical robustness of footholds for legged robots in unstructured terrain. In contrast to approaches that rely on human expert knowledge or human defined criteria to identify appropriate footholds, our method uses the robot itself to assess whether a certain foothold is adequate or not. To this end, one of the robot’s legs is employed to haptically explore an unknown foothold. The robustness of the foothold is defined by a simple metric as a function of the achievable ground reaction forces. This haptic feedback is associated with the foothold shape to estimate the robustness of untouched footholds. The underlying shape clustering principles are tested on synthetic data and in hardware experiments using a single-leg testbed.