Pandemic Legacy Season 1 September: Where to search if the conditions can’t be met?
From the Compiled FAQ on BGG, taken from the July spoiler:

What if there are no research stations in faded cities?
You will need to build one (or use Field Hospital ) if you wish to attempt the search.

So similarly, in September you'll need to build a military base in one of your faded cities.
I don't know what the thematic explanation is, but I'm sure you could retcon something - building a military base is actually commandeering an existing facility, or it just gives you the necessary infrastructure to find the soldier in the region, or he congregates to the base, or something.