동맹으로 확대되어 가는 영향력
제노가 사망하자 히포드로무스에 모여든 군중은 레오 1세의 딸이자 막 과부가 된 황후 아리아드나에게 새로운 통치자를 선택하라고 강요하면서 새 황제가 정통파 신자이자 이사우리아인이 아닌 로마인일 것을 요구했다. 아리아드나는 발칸반도 디라키움(지금의 알바니아 두러스) 출신으로 나이 많은 관료 아나스타시우스를 선택하고 후에 그와 결혼했다. 아직은 군대의 갈채가 즉위 과정에서 가장 중요한 요소로 남아 있었지만 아나스타시우스 1세가 총대주교가 주관하는 대관식을 치른 점에 주목해야 한다. 게다가 대관식에 앞서 칼케돈 신경을 인정하는 정통파로 남겠다는 다짐을 하도록 강요받았다.
여하튼 그는 제국 내에 남아 있는 이사우리아인들의 영향력을 성공적으로 다루었다. 제노의 형제 룽기누스는 유배형에 처해졌고, 이사우리아인들은 폭동을 일으켰다가 모두 콘스탄티노폴리스에서 추방당했다. 게다가 492년부터는 이사우리아인 사이에서 전쟁이 벌어졌다. 이 전쟁은 498년에 끝났으며 이후 이사우리아인들은 다시는 제국의 정치에서 주연을 차지하지 못했다. 황제는 비로소 단기적으로는 쟁정이 풍족해지고 장기적으로도 긍정적인 효과를 미치는 광범위한 개혁에 착수했다.
아나스타시우스의 대외 정책은 동맹 관계를 통해 비잔티움 제국의 영향력을 확대하는 것으로 정리할 수 있다. 이탈리아에서 오스트로고트의 테오도리크는 493년 오도아케르를 살해한 후 왕으로서 이탈리아를 지배했다. 아나스타시우스는 테오도리크를 무력으로 몰아낼 수 없기에 이를 인정했으며, 테오도리크의 이탈리아 지배는 평화로운 번영의 시대였다. 수도 라벤나에 지어진 건물 다수는 아직도 살아남아 그 시대의 영화를 전해 주고 있다.
테오도리크는 서방 황제의 지위에 오르지 않는 대신 서방의 주요한 패권국들(프랑크 왕국, 비시고트 왕국, 반달 왕국)과 결혼 동맹을 맺고 로마의 옛 원로원 귀족들과 협상을 통해 자신의 지위를 공고히 했다. 비잔티움 제국은 이에 대응하여 칼케돈 신경을 따르는 프랑크 왕국(이 시점에서 알프스 이북의 최대 세력이었다)과 외교적 친선을 추구함으로써 아리우스파를 따르는 고트인과의 사이에 적대감을 부추겼다. 아프리카 수복이 당장은 불가능하다는 판단에 반달과의 관계를 정상화했다. 발칸반도 북쪽에서는 튀르크계 불가르[당시 그리스어 사료들은 불가르를 캅카스 북방의 초원에서 발칸반도까지 거주하는 다양한 유목 집단을 가리키는 통칭으로 사용했다. 여기에서 불가르는 돈강과 드니프로강 인근에서 유목하던 쿠트리구르(Kutrighur)를 의미한다. 이외에도 아조우해 북방에 유목하던 우티구르, 카자흐스탄 초원에 유목하던 온오구르 등이 있다. 온오구르는 7세기 말 다뉴브강을 넘어 발칸반도 북동부에 정착하여 불가르 제국을 세운다. 훈, 튀르크계 부락이 중심이 된 불가르 제국은 이후 9세기 중반까지 차츰 토착 슬라브 주민들과 결합하고 정교회를 받아들이는데, 이때부터 해당 정치체를 불가리아라 한다. 이 때문에 비잔티움 사료들은 다뉴브강 이남의 불가리아와 흑해 북방에 있던 불가르를 구분하기 위해 흑해 북방에 있던 시절의 불가르 정치체를 ‘먼 불가리아(Magna Bulgaria)’ 또는 ‘옛 불가리아(Palaia Bulgaria)’라고 불렀다]가 비잔티움 제국 영토로 침입하기 시작했다. 콘스탄티노폴리스의 배후지인 트라키아 지역마저 수차례 약탈당할 정도였다.
동방에서는 502-506년 페르시아와의 전쟁이 있었다. 페르시아 왕 카바드 1세는 아르메니아를 침공한 뒤 대대적인 공성전을 통해 메소포타미아 지역의 아미다를 점령했다. 아나스타시우스는 페르시아 군대를 격파하기 위해 대군을 보내 모든 지역을 탈환하는 데 성공했다. 평화 협정이 맺어지기 전에 비잔티움 제국은 페르시아 방면의 국경을 강화하기 위해 요새 아나스타시우스폴리스(나중에는 다라라고 불렀다, 지금의 튀르키예 오우즈)를 건설하는 한편, 인근 여러 도시의 성채를 강화했다. 또한 페르시아와의 전쟁 과정에서 아나스타시우스는 아랍계 부락 연맹인 킨다 및 가산과 동맹을 맺었다. 그들은 페르시아 방면의 국경을 지키고 비잔티움 제국과 함께 싸운 대가를 받고 특권을 누렸다.
아나스타시우스 1세는 조카 셋이 제국의 주요한 지위에 올랐데도 후계가즐 세우지 않고 518년 거의 아흔 살 나이로 죽었다. 아나스타시우스가 합성론파의 지지자였던 점이 유스티누스 1세 즉위의 배경이 되었을 것이다. 유스티누스의 출신은 보잘것없었으나(사료들은 그가 달마티아 출신에 문맹이었다는 점을 강조한다), 승승장구하여 근위대장을 지낸 사람이다. 이 선택을 주도한 핵심 세력은 원로원이었으며, 민중의 갈채 의식은 비잔티움 국체의 신성함과 영광을 찬미할 뿐 아니라 새 황제의 정교성과 신의 보호를 결합시켰다.
유스티누스는 아나스타시우스의 대외 정책을 이어갔다. 그는 서방에서는 아리우스파인 오스트로고트를 고립시키고, 동방에서는 페르시아 방면의 방어를 강화했다. 비잔티움 제국의 영향력은 새로운 동맹을 통해 확대되었다. 제국은 캅카스 지방에서 라지카(조지아어로는 에그리시)와 이베리아의 충성심을 끌어내는 데 성공을 거두어 통치자들을 복속시켰다. 한편 남쪽에서는 그리스도교 악숨 왕국(지금의 에티오피아와 에리트레아)이 유대화된 유일신교를 추종하며 그리스도교를 박해하는 힘야르 왕국(예멘에 있었다)에 대항해 일으킨 전쟁을 지원했다.