In this paper we examine the interplay between terrain classification accuracy and gait in a walking robot, and show how changes in walking speed can be used for both terrain-dependent walk optimizations, as well as to enhance terrain identification. The details of a walking gait have a great influence on the performance of locomotive systems and their interaction with the terrain. Most legged robots can benefit from adapting their gait (and specifically walk speed) to the particular terrain on which they are walking. To achieve this, the agent should first be capable of identifying the terrain in order to choose the optimal speed. In this work we are interested in analyzing the performance of a legged robot on different terrains and with gait parameters. We also discuss the effects of gait parameter, such as speed; can have on the terrain identification by a legged robot. We use an unsupervised classification algorithm to classify terrains based on inertial measurement samples and actuator feedback collected over different terrains and operation speeds. We present the effects of speed on the terrain classification in our classification results.