Одним из самых важнейших деяний этого энергичного правителя стала организация не просто нового опорного пункта в Европе, а новой постоянной столицы Империи на Востоке. Город выстроили на месте известной еще Геродоту древней мегарской колонии Визáнтий, с VII в. расположившейся на побережье пролива Босфор.
Древнегреческая легенда гласит, что когда в 670 г. до н. э. жители города Мегары на западе Малой Азии решили основать новое поселение — апойкию, они, как полагалось, обратились за советом к прославленному оракулу бога Аполлона в Дельфах. По одной из версий мифа, предводитель колонистов с необычным именем Виз или Визáнт получил от оракула указание возвести город на фракийском мысу, где рыба и олени водятся в изобилии.
Прибыв на берега Мраморного моря, у южного входа в пролив Босфор, Визáнт и его спутники окинули взором прекрасный пейзаж и стали совершать положенное перед закладкой поселения жертвоприношение. Вдруг прилетел огромный коршун, схватил жертвенное животное и отнес его на холмистую оконечность особенно удобно расположенного Босфорского мыса. Посчитав случившееся добрым знаком богов, переселенцы решили на том месте, куда коршун унес добычу, построить город. Новая колония, по традиции, получила название Византий, по имени её отца-основателя, и избрала символом своего города полумесяц в честь покровительницы, богини Артемиды.
Во время гражданской войны в Римской империи в 196 г. город после двухлетней тяжелейшей осады, когда среди осажденных дело дошло до каннибализма, был разгромлен войсками могучего военачальника, сурового, безжалостного, неразборчивого в средствах, «солдатского» императора Септимия Севера, поскольку поддерживал его противника, Писцения Нигера. Но затем, после страшной расправы, он был возвращен к жизни, восстановлен и украшен, став еще больше по размерам.
Ранней осенью 324 г. римский император Константин, преследуя соимператора Валерия Лициния, своего разгромленного последнего соперника, окончательно разбил его у Хрисополя, малоазийского портового городка, который находился напротив Византия. Тогда то он и оценил на редкость удобное положение Византия как военно-морской базы на Мраморном море и Босфоре, которую можно защищать без особого труда, и решил устроить здесь сильный укрепленный пункт с императорской резиденцией, постоянными военными силами, мастерскими по изготовлению оружия, амуниции, имперскими конными заводами. Использовав доставшиеся ему богатства Лициния, он увеличил город в пять раз по сравнению с городом, восстановленным Септимием Севером, по сути дела, заложил его заново. Малоизвестный дотоле маленький гарнизонный городок Византий начал превращаться в растущий политический, торгово-экономический и культурный центр пока еще объединенной, единой Римской империи.
Предание, пересказанное вскоре после смерти Константина I, его биографом, Евсевием Памфилом, повествует, что, начиная строительство, император взял в руки копье, дабы самолично отметить им границы будущей столицы. Он все шел с ним и шел, чертя линию на земле. Сопровождавшие его придворные, видя чрезвычайные размеры города (около 370 гектаров), с удивлением стали спрашивать его: «Докуда, государь, ты пойдёшь?». Он же многозначительно ответил им, намекая на помощь небесных сил: «Я пойду до тех пор, пока не остановится некто, идущий впереди меня!». Там, где видимый только Константину небесный посланник вонзил в землю меч, и были заложены новые оборонительные стены. Император, имя которого со временем передадут городу, одновременно с языческим «освящением» в понедельник, 11 мая 330 г., в серебряный юбилей своего правления, посвятил Новый Рим — Неа Роми христианскому Богу, справив «Таинство Таинств» — Божественную литургию. Примечательно, что император появился на торжествах в диадеме — символе власти восточных деспотов, которой его римские предшественники избегали. В этом тоже крылся намек на новые отношения.