Since there were no trains, we had to walk the whole way.
Literal
Train [subject-が] did-not-exist so, we [topic-は] the-entire-way had-to-walk.
ない for 'none exist' on 列車がなかった — the negative of ある ('there is / exists'). ので chains it to the consequence. ずっと ('the whole way') + 歩く ('walk') = 'walk continuously the whole way.' ~なければならなかった is the past obligation — 'had to' in the past.