Originally Posted by
Caligula's_Horse
I only recently figured it out myself, and it took a couple of tries.
The trick is to spend a turn or two buying any additional troops you might need that require a military building to recruit (I got 3 cavalry units per army; I later added some extra spearmen, but you don't need a horde structure for those), and to liquidate any horde structures you have, as well as dismissing your unit of cataphracts (400 per turn per unit is unacceptable at this stage of the game). This ought to give you a war chest of some 20k to work with, and an income in the -3k or -4k range once you (immediately) take the first two towns, which is manageable, barely.
Then you start conquering and you don't look back; forget about holding territory, in the time it takes you to stabilize one province, you can capture two more; I lost two towns to rebels, during which time I took a whole new province and two thirds of another one. You're going to need all your money just to absorb the your negative income for the first 5-10 turns or so, so don't build anything just yet. Repairing structures damaged when a town was occupied is fine though, as its quite cost effective (usually pays for itself in less then a turn, so long as you didn't sack the town). Converting to Arian Christianity also helps slow down the rate of revolt. Embezzling funds through politics can also be a small help.
You're going to be outnumbered by the Vandals 2 to 1 for two or three major field battles; I found I could win without too much trouble by supplementing my inferior cavalry with a unit or two of spearmen per flank. Resistance more or less falls apart after that, especially if you can get the Berbers and/or Sardinians to join you against the Vandals (allying with the Berbers will also help with the Moors later, as some spawn in and near Berber territory). Use captives to replenish if the rate of conquest threatens to slow, and ransom them otherwise. Once the Vandals are no longer in play, head back and recapture anything lost to rebels. Then, stabilize your provinces, and get ready for the Moors; I found I had some 5-10 turns of breathing space between wiping out the last rebels and the invasion, which was plenty.
Once the Moors are dealt with, you're good to go; I recommend going after the Berbers (backstab them if you made an alliance) and Spain next rather then Italy though; Italy tends to put you on a collision course with Justinian, which is about as powerful as all the rest of the maps' factions combined. Best to keep your distance from the ERE for as long as possible.