Translation:The soldier does not fight between the cities.
Why nem is not right infront of the verb? Its more important cities than fighting? Maybe I'm missing the priority in this negation
As you already mentioned, it is because the emphasis is on the location and not on the fact that the soldier is fighting.
Nevertheless, "a katona nem harcol a városok között" as well as "a katona a városok között nem harcol" are correct sentences - but again with slightly different meanings.