Hay diferentes tipos de terreno en el mapa de aventuras; en algunos de ellos es más fácil moverse, mientras que en otros la movilidad del héroe se ve reducida. La cantidad de movimiento disponible en un turno por un héroe se expresa en puntos, y viene dada por la movilidad de la criatura más lenta que lleve consigo al comienzo del turno. Mover en terreno escabroso usa más puntos de movimiento que en terreno normal. Cada paso que des en terreno normal (hierba, campo) utiliza 4 puntos de movimiento, mientras que en otros tipos de terreno utiliza más puntos de movimiento. Además, mover diagonalmente en cualquier terreno requiere usar más puntos de movimiento que mover en horizontal (Este-Oeste) o en vertical (Norte-Sur).
A continuación se muestra una tabla con imágenes e información de cada tipo de terreno, incluyendo el tanto por ciento de movilidad sobre cada uno.

Debido a su especialidad, el movimiento de los Bárbaros no sufre penalización en terreno escabroso. Asímismo, las Hechiceras pueden mover el doble en el mar.
Puedes incrementar la movilidad de un héroe dejando en el castillo las tropas más lentas, y usando algún artefacto de movilidad.
Para explorar en terrenos abiertos (con pasos sin proteger) es buena idea usar un Bárbaro sólo con tropas rápidas, con lo que se cubrirá una gran extensión de terreno en poco tiempo. Esto permite capturar minas y recolectar recursos rapidamente, para ayudar a edificar en las villas y a reclutar más tropas para conquistar tus objetivos. También podrías conseguir algún que otro artefacto desprotegido.