Ирано-византийская война 502-506 гг. была неудачной для византийских войск. Захария Митиленский указывает, что среди причин неудач византийские полководцы называли отсутствие в окрестностях сильных укреплённых пунктов, в то время как противник располагал мощной крепостью Нисибис (принадлежавшей римлянам до её уступки в 363 г.).[1]

Поэтому, в 505 г., пока персидский царь Кавад I был занят на востоке, император Анастасий I решил перестроить деревню Дара, расположенную в 18 км. на запад от Нисибиса и в 5 км. от границы с Персией, с тем чтобы превратить её в мощную крепость, в которой можно было бы дать отдых армии и складировать вооружение. Со всей Месопотамии были собраны каменщики и строители, работавшие в большой спешке. Новый город был построен на трёх холмах, на самом высоком из которых стояла цитадель со складами, банями и цистернами для воды. Крепость была названа Анастасиополем (греч. Ἀναστασιούπολις).

Прокопий Кесарийский пишет[2], что из-за спешки при строительстве и суровых погодных условий крепость быстро обветшала, а некоторые участки стены обрушились. Император Юстиниан I был вынужден начать дорогостоящую перестройку крепости. Стены были выстроены заново, внутренняя стена была увеличена на один ярус, в результате чего высота её достигла 20 метров. Башни также были укреплены и стали трёхъярусными, свыше 30 метров в высоту, а вокруг был выкопан ров, заполненный водой.[3] После завершения работ крепость была переименована в Новую Юстинианию.

Чтобы обеспечить гарнизон водой был прокопан канал, направивший протекавшую неподалёку реку Кордес через город. Оборонявшиеся также могли перекрыть русло реки у выхода её из города, и направить его в естественную подземную протоку, случайно обнаруженную во время наводнения. Выход протоки на поверхность находился в 60 км. от города, что давало возможность лишить воды осаждающую армию и не раз спасало город[4]. Для защиты от наводнений (одно из которых в своё время нанесло большой ущерб укреплениям) была построена дамба.[5] При Юстиниане также были построены казармы и две церкви.[6]