Pohyb hrdinů je v Heroes II určován několika faktory. Ten asi nejdůležitější je rychlost nejpomalejší jednotky v hrdinově armádě. Čím pomalejší jednotku máte, tím méně bodu pohybu váš hrdina získá. Jedinou výjimkou je pohyb po moři, kde se rychlost nijak nemění. Druhým faktorem je terén, po kterém se hrdina pohybuje a zda jde po cestě či nikoliv. Dalším faktorem jsou dovednosti jako Logistika, Navigace či Hledání cest a v neposlední řadě také mnohé artefakty.
Pokud tedy vidíte cesty, které jdou přes nerovný terén, rozhodně je neberte jen jako dekoraci a naopak je využívejte ve váš prospěch, neboť někdy pár tahů znamená výhru (prohru).
Tabulka níže vám poodhalí, jak mají jednotlivé terény vliv na rychlost pohybu a jak jej ovlivňuje schopnost Hledání cest (200% postihu = ½ rychlost, 75% postihu = rychlejší pohyb o ¼):
| Terén |  Bez Hledání cest |
 Základní Hledání cest |
Pokročilé Hledání cest |
Expertní Hledání cest |
 Poušť |
200% | 175% | 150% | 100% |
 Bažina |
175% | 150% | 125% | 100% |
 Sníh |
175% | 150% | 125% | 100% |
 Pustina |
125% | 100% | 100% | 100% |
 Pláž |
125% | 100% | 100% | 100% |
 Láva |
100% | 100% | 100% | 100% |
 Voda |
100% | 100% | 100% | 100% |
 Hlína |
100% | 100% | 100% | 100% |
 Tráva |
100% | 100% | 100% | 100% |
 Cesta |
75% | 75% | 75% | 75% |
