Cuando Justiniano subió al trono del Imperio bizantino tenía formulados los principios de su política de Renouatio Imperii, que, entre otros aspectos, consistía en el restablecimiento del poder imperial en todos los territorios de los que había desaparecido. La península ibérica entraba, en consecuencia, entre los territorios que Justiniano podía recuperar para el Imperio.
Aunque la primera ocasión en que visigodos y bizantinos tuvieron un enfrentamiento fue en los años cuarenta del siglo vi —cuando se disputaron la soberanía de Septem (Ceuta)—, no fue hasta el año 552 cuando las tropas bizantinas pusieron pie en la Península Ibérica.
Según Jordanes, un autor contemporáneo a los hechos, Justiniano fue «invitado» a entrar en el reino visigodo: Atanagildo, pretendiente al trono visigodo, solicitó la ayuda militar del Imperio para acabar con el gobierno del rey Agila. Justiniano accedió a la misma, posiblemente obteniendo como contrapartida la cesión de algunos territorios peninsulares meridionales.
Sin embargo, el emperador debió conquistar más territorios de lo que se habría acordado como contrapartida por la colaboración solicitada, que, además, no debió ser en la medida en la que hubiera querido Atanagildo. Se considera que, durante los primeros años de presencia bizantina en la península, los soldados de Justiniano ocuparon la franja costera de territorio peninsular meridional y levantino, que se extendería entre la zona del Estrecho y el sur de Valencia, además de algunas amplias franjas interiores de territorio bético y cartaginés.
Sus principales ciudades serían Assidona (Medina Sidonia), Malaca (Málaga), Illici (Elche) y Carthago Spartaria (Cartagena), siendo muy posiblemente esta la capital de la Hispania Bizantina desde el 552.

En cualquier caso, Atanagildo resultó vencedor de su enfrentamiento con Agila, siendo una de sus primeras acciones el intentar acabar con la presencia imperial en territorio peninsular. Gracias a autores como Gregorio de Tours e Isidoro de Sevilla sabemos que logró recuperar algunos territorios, pero no consiguió expulsarles de la península.
En los últimos años de gobierno de ambos dirigentes (Justiniano falleció en 565 y Atanagildo en 567) surgieron problemas internos tanto en el Reino visigodo como en el Imperio bizantino. Ninguno podía dedicar más efectivos a su lucha; de ahí que firmaran un pacto que, verosímilmente, consistiría en un acuerdo de no agresión.
Tenemos noticia del mismo gracias a su mención en una carta que el papa Gregorio Magno envió en 595 al rey visigodo Recaredo. Con la firma de ese pacto, el Imperio reconocía la legalidad de la soberanía visigoda sobre un antiguo territorio imperial, pero también el Reino visigodo reconocía el derecho del Imperio a ejercer soberanía sobre algunos territorios peninsulares; se ponía al Reino visigodo en pie de igualdad con el Imperio. Leovigildo, sucesor de Atanagildo, lo comprendió y lo aprovechó, pues inició acciones militares contra los bizantinos.
Complejidad en Occidente
En 570 y 571, Leovigildo arrebató a los bizantinos importantes ciudades del sur de la península: en Bastetania conquistó Acci y Basti (Guadix y Baza respectivamente); intentó también conquistar, infructuosamente, Malaca, si bien tomó posesión de amplios territorios de esa región malacitana. Los bizantinos también perdieron Assidona.
Ese rey visigodo conquistó, además, territorios que escapaban a su control o al bizantino, como la Oróspeda o Córdoba, logrando con ello acercarse más a los territorios meridionales en manos del Imperio. La rebelión, en 579, del príncipe visigodo Hermenegildo contra Leovigildo, su padre, cambió el carácter de las relaciones entre visigodos y bizantinos.
Al igual que Atanagildo, Hermenegildo solicitó la ayuda del emperador, circunstancia conocida gracias a Juan de Biclaro, Gregorio de Tours o Gregorio Magno; a tal fin, el obispo Leandro de Sevilla viajó hasta Constantinopla, donde convenció a los emperadores Tiberio y Mauricio de que apoyar la causa del pretendiente visigodo reportaría al Imperio grandes ganancias territoriales en Hispania.

Así, los soldados bizantinos se involucraron, una vez más, en una querella dinástica visigoda, pero no del modo en que hubiera querido Hermenegildo. Excepto durante los momentos iniciales, todo parece indicar que los soldados bizantinos le prestaron poca ayuda directa; parece incluso que apenas le ayudaron a mantenerse militarmente activo.
De hecho, el que el episodio de Hermenegildo no se prolongara más en el tiempo se explica por el complejo panorama que el Imperio tenía en sus otras posesiones occidentales. Los lombardos habían invadido el territorio itálico del Imperio en 568, y su conquista hacia el sur se prolongó durante las siguientes décadas.
Imposibilitado el Imperio de hacerle frente de un modo efectivo debido a sus problemas militares en las fronteras orientales, logró que los reinos merovingios —algunos de cuyos dirigentes eran familiares directos de Ingunda, la esposa de Hermenegildo—, se comprometieran a crear dificultades a los lombardos en las fronteras septentrionales de Italia. Sin embargo, olvidaron ese compromiso para fijarse en un nuevo objetivo: entrar militarmente en el Reino visigodo para contribuir a la causa de Hermenegildo.
Ante esa tesitura, la prolongación de la rebelión de Hermenegildo no era favorable a los intereses imperiales. Es probable que esta fuera la circunstancia determinante que llevara a los bizantinos a aceptar un subsidio ofrecido por Leovigildo para que dejaran de apoyar al rebelde visigodo; Leovigildo también se habría comprometido a no atacar el territorio bizantino peninsular. El abandono del Imperio de la causa de Hermenegildo contribuyó enormemente a la derrota de este rebelde visigodo.
Hostilidad y breve concordia
Con el ascenso al trono de Recaredo, sucesor de Leovigildo, visigodos y bizantinos continuaron considerándose acérrimos enemigos: así entendemos que en el Imperio bizantino se considerara a los visigodos hostes barbari, como se lee en la inscripción bizantina de las murallas de Carthago Spartaria (año 589), al tiempo que desde el Reino visigodo las acciones del Imperio en Hispania en aquellos años —posiblemente conquistaron más territorios— eran calificadas como romana insolentia.
Recaredo intentó recuperar el territorio perdido; su objetivo estuvo puesto en las fronteras orientales de la Hispania bizantina, pues allí fundó dos obispados, Ello y Begastri, con el fin de acercar sus posiciones a las ciudades bizantinas de Illici y Carthago Spartaria. Recaredo intentó conocer, a través del papa Gregorio Magno, cuáles eran los territorios pactados durante los gobiernos de Atanagildo y Justiniano, posiblemente para intentar reclamar el cumplimiento del texto pactado.

Gregorio Magno le disuadió, arguyendo que tal pacto era contrario a sus intereses, lo que indica que, a pesar de todo, en el gobierno del emperador Mauricio (582-602) el territorio bizantino hispano era menor que el logrado por Justiniano a la firma del pacto. Durante el gobierno del emperador Mauricio, tres obispos hispano-bizantinos fueron depuestos o exiliados por las autoridades bizantinas, entre ellas, el conocido general Comenciolo.
Aunque las razones no son conocidas directamente, de la documentación epistolar papal podemos intuir que fueron acusados de traición al Imperio; es posible que estos prelados, entre los que se encontraban Liciniano de Carthago Spartaria y Jenaro de Malaca, consideraran entonces más interesante para sus diócesis el formar parte del Reino visigodo, que ya era católico.
La actuación del Imperio contra esos obispos deja claro que no estaba dispuesto a abandonar sus dominios en la península. Que Mauricio fuera el emperador explica este «renovado» interés por conservar el territorio imperial, pues fue el responsable de una nueva ordenación administrativa y militar del territorio del Imperio.
Esta acción se conoce como «Reforma Exarcal»; por primera vez aparecen los dominios bizantinos de Hispania, Septem y las islas Baleares en un documento de ese origen. Estos territorios quedaron enmarcados en la Eparquia Mauritania II, cuyo gobernador dependería, en primera instancia, del Exarca de Cartago.
La hostilidad continuará caracterizando las relaciones entre visigodos y bizantinos hasta c. 615. En torno a ese año tendrá lugar un cambio en las mismas, bien es verdad que cuando el territorio bizantino peninsular había sido reducido gracias a las exitosas campañas del rey visigodo Sisebuto y a la evidente inhibición del Imperio, pues el entonces emperador, Heraclio, dedicaba la mayor parte de su fuerza militar a contener el avance persa y ávaro sobre el territorio oriental.
Gracias a varias epístolas que intercambiaron el patricio bizantino al mando de las posesiones imperiales en España, Cesario, y Sisebuto, sabemos que los bizantinos iniciaron las negociaciones encaminadas a la firma de un tratado de paz. En estas epístolas comprendemos el cambio en la consideración del Imperio bizantino respecto al visigodo: el gobernador bizantino aludía a la común creencia católica que unía a imperiales y visigodos; el rey visigodo y el territorio que dominaba eran tratados por el bizantino como equivalentes al emperador y al territorio imperial.

Ello habla de las dificultades militares imperiales en todos los frentes abiertos, pero también de la ventaja militar de Sisebuto, quien, sin embargo, estaba abierto a la firma de una paz. Dichas negociaciones se desarrollaron tanto en Hispania como en Constantinopla; los legados enviados regresaron de esta ciudad con un rescripto del emperador Heraclio, firmado con su propia mano, en el que se debía acordar el cese de hostilidades, y el reconocimiento mutuo de los territorios.
La concordia debió durar pocos años, pues Suintila, sucesor de Sisebuto, emprendió operaciones militares exitosas contra los territorios bizantinos, tanto que le permitieron conquistarlos en su totalidad, incluida la ciudad que había sido su capital, Carthago Spartaria, que, según Isidoro de Sevilla fue arrasada por los visigodos en torno al año 625. Este gesto de Suintila indicaría su intención de anular cualquier recuerdo de la presencia bizantina en territorio peninsular hispano.