Choosing Place Names
Just like choosing the names of characters, choosing appropriate names for places can really add an extra layer of believability to your mission.
Towns and Cities
Older towns and cities, or those closer to the center of the Empire, will often have names with a Latin influence (eg, Vinovia, Lindum). Other, newer towns will have more British-sounding names (eg, Aberarad, Halstead, Coniston). Cities that have a large port often have "port" at the end of their name (Bridgeport).
Towns on the western or northern edges (conquered later in the Empire's history) will probably have names that sound more Germanic (eg, Flensburg, Braeden, Esslington).
Street Names
It was normal practice for a medieval street name to reflect the street's function or the economic activity taking place within it. As time passes and people move around the city, however, the names often have little to do with the people who live there. It's not uncommon for no bakers to live on Baker Street.
Examples: Friar Lane, Lime Street, Tanner's Market, High Road, Ironmonger lane, Candlewick lane, Eastcheap.
For some amusing examples of some more vulgar medieval street names, see [this Wikipedia article].