Столкнувшись с растущими проблемами управления огромным государством, Диоклетиан в 293 году разделил власть над Римской империей между двумя соправителями, что со временем привело к распаду страны на восточную (греческую) и западную (римскую) половины. Внешние границы империи редко бывали спокойными, так что так называемый Pax Romana (римский мир) оставался не более чем мечтой. «Римский мир» заключался в бесконечной войне с варварами на севере, на западе и на юге и с более развитыми древними государствами на востоке. Безопасность империи зависела от ее длинных укрепленных границ, особенно по Рейну и Дунаю. В конечном счете армия и чиновничий аппарат, на которых держалось государство, оказались не только разорительными для казны, но и ненадежными, и набеги германских племен завершились нашествиями варваров в IV–V веках.

Консервативные современники объясняли все беды Рима распространением христианства, которое росло, несмотря на официальные гонения и внутренние расколы. Судьбы империи и религии объединил Константин, чьи войска в 306 году объявили его императором Запада. Шестью годами позже он принял христианство и в 324 году разбил своего соправителя, Лициния, в битве у Геллеспонта — первом крупном сражении флотов в Средиземноморье за 350 лет. У Константина было 200 триаконтер и пентеконтер против 350 трирем Лициния. Что бы ни определило победу Константина — талант флотоводцев, которые отрядили в бой лишь часть судов, обеспечив им бо́льшую свободу маневра в узком проливе, или шторм, выбросивший корабли Лициния на берег на второй день битвы, — поражение сломило Лициния; вскоре он был схвачен и казнен.

Константин провозгласил своей столицей Византий, который в 330 году был переименован в Константинополь и со временем остался единственной столицей империи, которую современники называли Ромейской (Римской), а более поздние авторы — Византийской. Расположенный на полуострове в южной части Босфора, у выхода в Мраморное море, Константинополь (ныне Стамбул) был крупнейшим перекрестком торгового сообщения между Азией и Европой и между Черным морем и Средиземным: первая крупная европейская столица, основанная как порт. Главным соображением при выборе места для Константинополя стало его географическое положение, которое давало «тихое пристанище мореходам», особенно вдоль Золотого Рога — четырехмильной бухты к северу от полуострова, «пригодной для якорной стоянки на всем своем протяжении». Что не менее важно, длина побережья позволяла разместить торговые и боевые суда коммерческого, политического и экономического центра империи. Как все дороги некогда вели в Рим, так все морские пути вели теперь в столицу Византии. Она быстро росла, и в VI веке, при Юстиниане I, в Константинополе и окрестностях проживало примерно восемьдесят тысяч человек. Даже после возникновения ислама в VII веке и появления итальянских морских республик в XI Константинополь благодаря своему размеру и стратегическому положению остался в первых рядах европейских и средиземноморских городов.

Через полвека после основания новой столицы варварские племена прорвали Рейнско-Дунайскую границу, что со временем привело к гибели Западной империи и возникновению новых государств от Британии до Северной Африки. В 410 году вестготы перешли Дунай и разграбили Рим. Император Гонорий вынужден был отозвать последние римские легионы из Британии и заручиться помощью вестготов, чтобы оттеснить вандалов в Испанию. В 429 году вандалы под предводительством Гейзериха переправились через Гибралтарский пролив в Северную Африку и первыми за пятьсот лет оспорили власть Рима над Средиземноморьем. Обосновавшись в богатом, но плохо защищенном Карфагене, вандалы вышли в море и утвердились на Балеарских островах, на Корсике и на Сардинии, откуда могли совершать набеги на материковую Италию, Иллирию и Грецию. В 455 году Гейзерих безнаказанно разграбил Рим, а в 476 году последний западный император был сослан на неаполитанскую виллу, выстроенную римским полководцем Лукуллом после Митридатовых войн.

К началу VI века северное побережье Средиземного моря было разделено между византийцами, остготами Северной Италии, вестготским Тулузским королевством в Юго-Западной Франции и вандалами в Испании. Византия в целом поддерживала с остготами хорошие отношения, однако Юстиниан стремился укрепить имперскую власть на западе, чтобы защитить морскую торговлю от вандалов и вестготов — в точности как на востоке пытался подорвать фактическую монополию персов в индоокеанской торговле. В 533 году полководец Велизарий по приказу Юстиниана пустился в морской путь с девяносто двумя боевыми кораблями и пятьюстами транспортными. Он захватил Северную Африку и Сардинию и одержал победу, положившую конец королевству вандалов. Затем Велизарий двинулся против остготов в Италию, овладел Сицилией, Неаполем и Римом, однако война затянулась, а Юстиниан не слал подкрепления, в том числе потому, что опасался популярности Велизария. Тем не менее к середине столетия византийцы отвоевали Италию, Сицилию и побережье вестготской Испании, в том числе порты Севилья и Кордова на Гвадалквивире и Сеуту на другой стороне Гибралтарского пролива. За исключением запада Северной Африки и франкского и вестготского берега от Сагунта до итальянской границы, прибрежная часть Средиземного моря вновь оказалась под властью одной державы. Однако относительно сильное торговое и военное присутствие Византии в Средиземном море не компенсировало ее слабость на суше, и период имперского возрождения оказался кратким. К началу 600-х годов лангобарды из Центральной Европы захватили почти всю Италию, авары подошли к стенам Константинополя, а в 624 году вестготы окончательно изгнали византийцев из Испании. Впрочем, ни одна из новых западных держав не стремилась овладеть морским потенциалом завоеванных земель, так что Византия по-прежнему могла поддерживать судоходную связь с центрально-средиземноморскими территориями.