You need a Docks/Port. Whatever it's called.
You need tradable goods in the original province.
You probably need Merchants (and upgrades).
You also need ships in every portion of the sea that borders a province you wish to trade with.
Do you have ships out everywhere? It's expensive, and when you go to war, it's SO easy to be blockaded. But the payoffs, woof!
Bookmarks