서방 곳곳에 게르만 왕국들이 생기면서 서로마 제국은 점점 약해졌고, 476년에 완전히 무너졌습니다. 서고트 왕국은 418년에 성립해 갈리아를 거쳐 스페인으로 중심을 옮겼고, 반달 왕국은 북아프리카를 장악해 439년에 카르타고를 수도로 삼았습니다. 동고트 왕국은 테오도릭이 493년에 이탈리아에서 세웠습니다. 이들 왕국은 오랫동안 서지중해를 지배했고, 동로마 제국은 그 틈에 힘을 회복했습니다.
재정복은 533년 반달 전쟁으로 시작되었습니다. 벨리사리우스는 소규모 병력으로 북아프리카에 상륙하여 놀랍도록 빠른 승리를 거두었습니다. 그는 1년 만에 아드 데키뭄과 트리카마룸 전투 에서 겔리메르 왕을 격파하고 카르타고를 함락시켜 반달 왕국을 영원히 멸망시켰습니다. 이 성공은 유스티니아누스가 다음 목표를 이탈리아로 잡도록 고무시켰습니다.
그러나 고트 전쟁(535–554년)은 훨씬 더 험난했습니다. 벨리사리우스는 시칠리아와 나폴리를 빠르게 점령하고 536년 로마를 수복했습니다. 하지만 토틸라 왕의 지휘 아래 동고트족이 반격하여 이탈리아 대부분을 되찾았고, 전쟁은 반도 전체를 황폐화시키는 잔혹한 교착 상태로 빠져들었습니다. 결국 나르세스 장군이 552년 타기나에 전투 에서 토틸라를 격파하며 마침내 승리했습니다.
이탈리아가 전화에 휩싸인 동안, 스페인의 서고트 왕국에서 내전이 발생하자 유스티니아누스는 이를 틈타 552년 소규모 원정대를 보냈고, 남부 해안 지역(스파니아)을 차지했습니다. 554년경 지중해는 다시 '로마의 호수'가 되었지만, 그 대가는 막대했습니다. 이탈리아는 인구가 급감하고 폐허가 되었으며, 제국의 자원은 고갈되어 미래의 위협에 취약해졌습니다.