Завоеванный край был отдален от Московского государства огромными степными просторами и территориально жил совсем обособленно. Летом сообщение с Москвой проходило по Волге, зимой — по степи. Но порой эта связь полностью и надолго прерывалась из-за хозяйничавших на Волге казачьих отрядов, а в степи — крымцев и ногайцев. Поэтому охрана покоренного царства требовала мер особой военной предосторожности. Главной заботой первого астраханского воеводы И. Черемисинова, начальствовавшего вместе с товарищем своим Михаилом Колупаевым, стала охрана перевозов через Волгу и охрана налаживающегося торгового пути по этой реке. Такой же заботой являлось и содержание крепости в боевой готовности.
Но старая татарская Астрахань не имела естественной защиты и сильных укреплений и потому была слишком уязвима при вражеских набегах со стороны Крыма и Северного Кавказа. С разрешения Москвы воевода, строго исполняя государев наказ «охранять покоренное царство Астраханское», решил обосноваться и укрепиться в другом месте. Осмотрев ближайшие окрестности города, он в 9 верстах ниже татарской Астрахани, среди многочисленных бугров, нашел один, значительно превосходивший размерами и высотой все другие.
Город перенесли на левый берег Волги, где были лучшие условия для его обороны. Строительство новой Астрахани началось в 1557 году на высоком Заячьем бугре, круто обрывавшемся к основному протоку Волги Центральная часть бугра не заливалась водой даже в самое сильное половодье, это место и решили обнести рвом и деревянной стеной. А кроме того, сам Заячий бугор с запада и севера омывался Волгой и ее рукавами, а с юга и востока его окружали непроходимые ильмени и болота, поросшие камы-щом и лесной порослью, что делало их практически непроходимыми.
Сотни стругов везли из Нижнего Новгорода строительный лес, а вместе с ним работных людей и стрельцов. Управлял строительством кремля опытный зодчий Иван Выродков. В первое время Иван Черемисинов не мог, конечно, поставить новый город чисто русским по внешнему облику: не было под руками в достаточном количестве главного материала — дерева, а получать его с севера было нелегко. Но к 1574 году в Астрахани под зашитой деревянных стен появился первый деревянный монастырь — Троицкий, ставший оплотом православия на этой земле, но до нас дошли только упоминания о нем.
Стратегические интересы России на юго-восточных рубежах государства требовали дальнейшего укрепления Астрахани, и в 1582 году в городе началось строительство каменного кремля. По указу царя Федора Иоанновича велено было возвести 8 больших башен в опасных местах, а в других — малые башни с тремя бойницами на каждой из них. Строительные материалы для их возведения привозили из прежней татарской столицы Сарая, а руководили строительством присланные из Москвы мастера Михаил Вельяминов и Дей Губастый. Башни нового кремля разделялись на несколько боевых ярусов, соединенных меж собой проложенными в толще стен переходами. Толщина стен самой мощной Крымской башни достигала 3,5 метра: башня имела 5 боевых ярусов и 20 бойниц. Сквозные проходы через башни соединяли боевые площадки стен, что позволяло действовать при обороне по всему периметру крепости.
Белокаменный, с отделкой из расписных изразцов, кремль как бы венчал глинисто-рыжий холм, под которым катила свои волны голубая Волга. Было чем залюбоваться, и недаром летописец восклицал:
«И зделан город бесчисленно хорош, а кругом его пояс мраморен, зелен да красен, а на башнях тако же.»
Украшением Астраханского кремля стал Успенский собор, на месте которого сначала находилась деревянная церковь, посвященная воспоминанию сретения иконы Богоматери, которую прислал Иван Грозный в 1564 году — через 14 лет после завоевания Астрахани. В 1602 году на этом месте была возведена каменная церковь в честь Успения Пресвятой Богородицы. В 1698 году из-за непрочности стен и сводов церковь была разобрана, и митрополит Самсоний приступил к возведению ныне существующего собора, строительство которого закончилось в 1710 году.
Успенский собор был возведен в византийском стиле с пятью главами и четырехконечными крестами на них. Вокруг собора была устроена каменная галерея, на которой основывается другая крытая галерея, идущая вокруг верхнего этажа. Верхний этаж храма — высокий и светлый, в нем проходили праздничные службы в теплое время года. В нижнем храме — сводчатом и полутемном — проходили службы зимой: одновременно он был и усыпальницей астраханских иерархов. В середине XVIII века здесь были захоронены грузинские цари Вахтанг VI и Теймураз II — сторонники дружбы с Россией.