Начало правления Анастасия было омрачено мятежом исаврян. Зенон не только сформировал императорскую гвардию из своих соотечественников, но и назначил исаврян на многие гражданские должности, и постоянно предлагал им обосноваться в Константинополе и заняться торговлей. Они были немало раздосадованы, когда скипетр перешел к иллирийцу Анастасию, и организовали заговор, намереваясь схватить его и объявить императором брата Зенона Лонгина. Через несколько месяцев после восхождения на престол Анастасия исавряне взбунтовались и захватили часть города в непосредственной близости от дворца. Однако народ их не поддержал, и после напряженных уличных боев, во время которых сгорел большой ипподром, восстание было подавлено. Лонгин был схвачен и принял сан. Он прожил довольно долгую жизнь и умер священником в Египте. Анастасий после мятежа уволил всех исаврян. Они вернулись в свои родные горы в Малой Азии и организовали мятеж там. Второй Лонгин, военный магистр во Фракии, возглавил восстание, которое продолжалось пять лет (491–496), но никогда не представляло серьезной опасности для империи. Мятежников разбивали всякий раз, когда они спускались с гор на равнины. Они продержались так долго благодаря наличию горных замков, которых в тех краях было немало. В 496 году был взят штурмом последний оплот исаврян, а их вождь, бывший военный магистр, схвачен и казнен. Анастасий карал самых упорных мятежников, отправляя их во Фракию, где они обустраивались в предгорьях Балкан. Император считал, что эти закаленные горцы не пропустят варваров из-за Дуная.
В азиатских провинциях империи не было никаких проблем до 502 года, когда началась война между Анастасием и царем Персии Кавадом. На месопотамской границе целый век было спокойно. После неудачной экспедиции Юлиана в 362 году не произошло ни одной серьезной войны с великой восточной монархией. Тот же век, что видел тевтонские миграции в Европе, на внутренних территориях Азии был отмечен повышением активности гуннов и других туранских племен за Каспием. Пока римские императоры были заняты на Дунае, Сасаниды защищали границу на Оксусе. Во время передышки в восточных проблемах Кавад потребовал у Анастасия деньги, император отказался, и началась война. Вначале римляне потерпели ряд неудач. Главная крепость Месопотамии Амида была взята штурмом в 503 году. Тогда же пал Нисибис (Нусайбин). А когда Анастасий послал на восток подкрепление, он назначил так много независимых командиров, что армию не удалось объединить. Отряды были разгромлены поочередно. В 504 году удача наконец улыбнулась римлянам. Тогда командование было поручено магистру оффиций Целеру. После длительной осады он вернул Амиду и начал движение через персидскую границу. Кавад в это время отбивался от гуннов и потому с радостью заключил мир на весьма неплохих условиях. Граница восстанавливалась на том же месте, где она проходила в 502 году. Анастасий сделал попытку предотвратить грядущие войны, построив две новые крепости на персидской границе – Дара в Месопотамии и Феодосиополь – севернее, на границе с Арменией. Они помогли сломить натиск персов тридцатью годами позже, когда снова сошлись в бою преемники Кавада и Анастасия. Персидская война, как и исаврийская, затронула лишь ограниченный регион – провинцию за Евфратом, вылазки не достигали Сирии. На самом деле за все время правления Анастасия единственной проблемой, затронувшей азиатскую часть империи, был набег гуннов из-за Кавказа, который в 515 году принес беды и разрушения Понту, Каппадокии и Ликаонии. Это вторжение оказалось изолированным, и за ним не последовали набеги кочевников северных степей.
Судьба европейских провинций, как и во времена Зенона, оказалась суровее. Славяне и бургунды систематически переправлялись через Дунай и вторгались через покинутые равнины Мезии во Фракию. Не единожды булгары громили римскую армию в поле, и со временем они продвинулись так далеко на юг, что Анастасий построил в 512 году стену, носящую его имя, от Черного моря до Пропонтиды, тридцатью пятью милями западнее Константинополя. Эти линии, тянувшиеся на пятьдесят миль через восточный выступ Фракии, служили для защиты по крайней мере ближайших окрестностей столицы от беспокойных всадников из-за Дуная. Македония и Иллирия, по-видимому, страдали меньше Фракии в этот период. Граничившие с ними славяне пока еще были не такими опасными врагами, как булгары, а остготы Италии, завоевав Паннонию, оказались более тревожными соседями для северо-восточной провинции империи, чем были веком раньше.