This research is aimed at investigating the interaction for a bipedal humanoid robot during locomotion on deformable terrains. The knowledge of deformable terrain properties has major implications in modelling the robot walking dynamics, which is the key to achieve stable gait patterns. We propose an in-situ terrain classification and estimation method in this paper to provide robots with such terrain properties. In particular, we introduce our method for classifying known terrains using recurrent neural networks (RNNs) and estimating the unknown terrain’s stiffness adopting the Bernstein-Goriatchkin model. We present our experimental procedures and analysis of the resulting data using NASA’s humanoid robot, Valkyrie, while it is performing a set of prespecified motions on different terrains, including gym foam mat, wood mulch, rubber mulch, and sand. It is concluded that using RNNs, we can efficiently classify the terrain types. For unknown terrains, our approach can estimate the terrain’s stiffness that demonstrates support forces under deformation.