Here are the maps for the provinces, if you can't find them in the game.

Krizsan Province - this is where you emerge out of Fort Emergence. This province has a slime infestation. Krizsan is situated in SW Valorim and its capital is also called Krizsan.
Isle of Bigail - this large island is home to the Anama church and also a huge nest of disease spreading 'roaches. Shayder is its capital city. The isle is situated north of Krizsan and south of the Marish peninsula, and can be reached from Farport (Krizsan), Softport (Midori) and Marish.
Karnold Province - Karnold province is in south east Valorim and has a troglodyte problem in the northern part. It is one of the sparsest populated provinces (it is heavily wooded in most places). The largest city is Sharimik
Midori Province - Midori Province is in mid Valorim and is affected by giant raiding parties to the south. Its capital city is Lorelei.
Footracer Province - Footracer is in north west Valorim and most of it is quarantined off by a large magical wall, to keep the alien beasts in. This used to be one of the most important provinces as it had the Keep of Tinraya in it, a major fort (this was completely destroyed by the alien beasts, and is in the quarantine area. Now the capital is Blackcrag Fortress.
Monoroe Province - this north east province is in a bad state. Maddok Isle has been lost to undead, the golems (powerful rock based monsters) are gaining territory, and the capital city, Gale, has fallen in to corruption and the scribbane herb. The only town having any success is Tevrono.