Leģenda vēsta, ka Stohova ir Bohēmijas svētā aizbildņa Svētā Vāclava dzimtā vieta. Vāclava māte Svētā Ludmila tam par godu esot iestādījusi ozolu. Vāclavam veltītais ozols (Svatováclavský dub) vēl aizvien atrodas pilsētā. Ozols gan tiek vērtēts kā 700 - 900 gadus vecs t.i. jaunāks nekā Svētā Ludmila, kas dzīvoja 10. gadsimta sākumā.
Rakstos pirmoreiz minēta 1316. gada. Ilgu laiku tā atradās Hābsburgu impērijas sastāvā. No 1919. gada — Čehoslovākijā. Strauji attīstījās 20. gadsimta otrajā pusē, kad pilsētā izbūvēja mājas apkārnes ogļu raktuvju strādniekiem. 1967. gadā Stahovai tika piešķirtas pilsētas tiesības. Kopš 1993. gada — Čehijā.