Как свидетельствует летопись, в 1221 году великим князем Владимирским Юрием Всеволодовичем основан был Нижний Новгород, защитой которому служили деревянно-земляные укрепления. Первая попытка замены деревянной крепости́цы ([разг.] крепостцы́) на каменный кремль относится к 1374 году. В это время князь Дмитрий Константинович заложил белокаменный кремль.

При Иване III Нижний Новгород играет роль пограничного города, имея постоянное войско, и служит местом военного сбора при действиях Москвы против Казани. В целях усиления обороны города вновь были начаты работы над устройством крепостных стен. Началом строительства каменного Нижегородского кремля стала закладка в 1500 году в верхней части города Тверской (ныне Кладовая) башни. Работа была прервана набегом орды хана Мухаммед-Амина в 1505 году. Возобновлено строительство было в 1508 году. При этом сохранявшийся старый дубовый кремль был уничтожен в сильном пожаре 1513 года. Завершено строительство, как предполагают, где-то после 1516 года. Основные работы по сооружению кремля осуществлялись под руководством присланного из Москвы архитектора Пьетро Франческо (Петра Фрязина). В XVI веке кремль многократно подвергался осадам и приступам (в 1521, 1536 и 1574 годах), при этом ни разу не был сдан осаждающему войску. К 1697 году кремль утратил военное значение.

Двухкилометровая стена имела 13 башен: 5 — прямоугольных в плане — являются проезжими или воротными и 8 башен — круглые глухие. Перед Дмитровской башней имелось выносное укрепление — каменный мост с отводной башней, что было новинкой в русском крепостном зодчестве.

С нагорной стороны кремль был окружён так называемым «сухим рвом» глубиной от 2,5 до 4 м и шириной примерно 25—30 м. Предполагают, что ров мог иметь отдельные углублённые участки, заполненные грунтовыми водами. Это касается района Дмитровской башни. Но в Писцовой книге 1622 г. говорится о копке рва глубиной 1 сажень (около 2,5 м) и шириной около 4 саженей (10 м) напротив всей линии стен в верхней части. Во всяком случае, это может быть ров во рву (кювет), так как сухого рва оказалось недостаточно. В этом новом рву и могла стоять грунтовая вода. А в сухом рву воды быть не могло, так как башни были погружены в него на целый ярус. Бойницы этого уровня, вместе с бойницами в дополнительных боковых казематах прясел (стен), представляли собой нижний или подошвенный бой. (В XVII в. ров появился и в подгорной части — на небольшом участке перед Ивановской башней.) Имеются сообщения о случаях обнаружения подземных галерей, расположенных глубже подошвенного боя и соединяющих некоторые башни. Но этот вопрос не был исследован.

«Каменный город» имел постоянный гарнизон. Об артиллерии кремля в XVI в. ничего не известно. Хотя устройство крепости позволяло при необходимости увеличить артиллерию многократно, в XVII в. артиллерийское вооружение Нижегородского кремля было сравнительно невелико, так как после взятия Россией Казани в 1552 году его военно-оборонное значение значительно снизилось. В 1621 г. в кремле имелось 22 пушки, в 1663 — 20, в 1619 — 19. Бо́льшая часть его орудий — это малокалиберные затинные (то есть крепостные) «пищали малого наряда» — волкони и гораздо меньше было пищалей среднего и крупного калибра. Имелись также единичные тюфяки, стреляющие дробом. Большинство пушек было медными и только несколько — из железа. Часть орудий стояла на подставках — «собаках», часть — на колёсных лафетах. Кроме артиллерии в обороне, конечно, применялось и ручное огнестрельное оружие, например, пищали-гаковницы (крепостные ружья), а в подвалах башен хранилось, вместе с запасом пороха, всевозможное холодное оружие.

В январе 1714 года Петром I была образована Нижегородская губерния. С этого времени Кремль стал административным центром Нижегородской губернии и центром Нижнего Новгорода.

При Екатерине II в 1785—1790 годах был произведён ремонт кремля, в ходе которого была разобрана кровля, лежавшая на зубцах стены, а сами зубцы были укорочены более чем наполовину. После снятия кровли, под воздействием атмосферных осадков, кладка кремлёвских стен стала постепенно разрушаться. Были разобраны выносные укрепления главной башни, а в 1834—1837 гг. был засыпан ров, что понизило высоту кремля примерно на 4 м. При этом нижние ярусы башен оказались под землёй, что привело к затапливанию их грунтовыми водами и постепенному разрушению. Тогда же весь Кремль был побелён, а его крыши перекрашены в красный цвет.