The Roman Fleet did not disappear with the collapse of the empire; it merely continued operating under new management. Roman ships had been crewed predominately by non-Romans (Greeks, Egyptians, Dalmatii) ever since the end of the Republic anyway, so adding the Teutons to the mix was just more of the same.

Byzantium considered itself the inheritor of Rome's empire and culture, but the Vandals and Visigoths ended up with most of the gear. By capturing of the port of Ostia, the Visigoths "inherited" that portion of the Roman fleet anchored there; the Ostrogoths seized the main Roman naval base at Ravenna together with contents, while the Vandals' steady capture of everything docked along Spain's coast rapidly made them a major naval power. (No minor achievement for a people whose original home was in landlocked central Europe.) There were fleets all over the place waiting to be picked up. Even when the Visigoths lost one in a storm while attempting a poorly-planned raid on the grain coasts of Sicily, it did not seriously discommode them.

In the post-Roman period, the dromon (Gr. "runner") -- a fast, maneuverable galley carrying sixty oars in a single bank, and with a full deck instead of just catwalks over the rowers -- became the mainstay of the fleet. This continued a trend already begun under the empire, where the trireme given way to the lighter 2-banked liburnian galley. Small ships with well-trained crews were far more effective. The lead dromons in the fleet would dye the top third of their sails red so that the rest of the ships could follow them more easily. (Later, Venetian ships often painted their hulls vermillion, probably for a similar purpose.)

By AD 440, the Mediterranean west of Sicily for all intents and purposes had become a private Vandal lake. They raided and looted what was left of 'civilization' every spring. Despite contributing "vandalism" to Europe's vocabulary, the Vandals actually did relatively little damage. With their keen eye for value, they preferred to keep the art treasures intact. According to a contemporary anecdote, Vandal helmsmen did not even bother to set courses. They simply raided wherever God's good wind (the Vandals were devout Christians) took them.

In those days, coming home from a regatta with 'hardware' really meant with hardware. As in, other people's. In 460, the Vandals put the proverbial cap on the mustard jar by capturing the poorly-defended port of Cartagena with 160 galleys still inside, virtually all that remained of the Roman Empire's fleet. The Vandal fleet's instant Division I status, (any fleet over 100 galleys automatically qualifies you for Div. I) meant they were ready to take on Constantinople.

Meanwhile, the Goths were the up-and-coming rowing power in the eastern Med. Their record on the waves was not as consistent as the Vandals' (Goths freely admitted water was not their preferred element), but the red eagles did very well when pressed, defeating a Vandal fleet off of Corsica, scattering several Byzantine fleets, but loosing one of their own because of poor ship handling and collisions within their own fleet.

In AD 468, Byzantium sent a huge fleet (1113 ships) to deal once and for all with the Vandal occupation of Carthage. When the overconfident Byzantine ships anchored for a night in a bay some 40 miles from Carthage, the outnumbered Vandal fleet filled many of its own galleys with combustible materials, towed them to the mouth of the bay, ignited them, and let the wind carry the fire galleys into the packed Byzantine fleet. The results were as visually spectacular as they were tactically persuasive. More than 600 Byzantine ships sank, burned, or were captured.

"Our navy is quite impressive, but we would get destroyed in a land war"*
Despite their prowess on water, the Vandal and Ostrogothic kingdoms eventually succumbed to the Byzantine army's overwhelming numbers. The Visigothic kingdom in Spain collapsed in the face of the Arab invasion early in the eighth century. Byzantium somehow survived its own corruption into the medieval period, its primary contribution to naval history: building expensive fleets for other people to sink. Meanwhile, a group of small islands on the Adriatic coast - whom the Byzantine Empire initially considered a tributary -- was putting together a rowing program which -- for sheer size, skill, and professionalism -- would one day eclipse anything the Mediterranean had yet seen.

* In Vandalspeak, "Classis gravis est, exstingemur in bello terrestri": an observation sometimes misattributed to Geselic, king of the Vandals; the source is actually W. F. Porter.