New towns?

Can you only get to new towns by doing missions or just walk there?

Most you can walk to, but that doesn't mean it's faster.

Some of the new towns you have to do missions. The towns in the northern half of the map are all accessible with walking.