Стены стояли на сплошных ленточных фундаментах из бутовой кладки. Подушка их была выложена с наружной стороны из рваного камня, а с внутренней непосредственно от подошвы основания начинается кладка из правильных прямоугольных каменных блоков. Выше подушки идет с наружной стороны наклонная, а изнутри кремля вертикальная кладка, облицованная камнем.
Фундаменты стен верхней части кремля основаны на мощном слое лессовидного суглинка, стены, стоящие на склонах, — на плотном мергеле или на слежавшихся древних оползневых накоплениях. Все эти грунты достаточно надежны, если в них не проникает вода. На прясле Георгиевская — Борисоглебская при устройстве фундаментов смело применена кладка уступами. В двух местах, где перепады высот оказались слишком большими, в кладке фундаментов были сделаны разрывы, а стены соединены кирпичными арками пролетом 7 и 7,5 м, которые держат массив стены в 13 м высотой от земли до боевого хода. Обе арки заложены кирпичными стенками толщиной около 1,5 м, непосредственно поставленными на грунт.
В Нижней части склона на прясле Белая — Ивановская, где грунт имеет значительную примесь песка, фундамент выкладывали в опалубке, поэтому верх его оказался во многих местах шире, чем подошва. На прясле Борисоглебская — Зачатская обнаружены остатки свайного основания, которое, по-видимому, относится к работам XVII века. Сваи под фундамент стены забивали между Борисоглебской и Белой башнями и при последующих ремонтах XVIII–XIX веков.
Кладка фундамента непосредственно переходит в кладку стены. Определить границу между ними можно только там, где меняется материал облицовки, так как камень обязательно выступал на три-четыре ряда над землей, и только выше мог быть заменен кирпичом. Толщина этой облицовки была не менее полутора кирпичей: «А в тех стенах делано с обе стороны с лица кирпичем, а промеж кирпичю кладен бутовый камен белой с ызвестью», — сказано в смете 1651 года Семена Задорина. Такая конструкция каменных стен была повсеместно распространена во времена средневековья.
В процессе реставрации Нижегородского кремля специально зондировались и изучались подземные части стен, включая исследование нижней плоскости подушки фундамента. При этом оказалось, что стены в последующее время не были усилены или расширены. Однако облицовка менялась на некоторых участках неоднократно, целиком или частично, причем камень заменялся более дешевым кирпичом. Такие вкрапления кирпича в каменную поверхность стены особенно ясно были видны до реставрации наружной стороны прясла Георгиевская — Борисоглебская. Материал там был сменен в XVII и XVIII веках, и время совершенно стерло границы работ разных периодов, так что различить их по наружному осмотру стало невозможно. На прясле Северная — Тайницкая под давлением насыпного грунта произошли сдвиги отдельных частей стены, которая после перекладки почти на всю толщу стала кирпичной. На пряслах Коромыслова — Никольская, Пороховая — Георгиевская и Часовая — Северная кладка велась горизонтальными рядами, на всех остальных ряды ее имеют продольный уклон вдоль стен, очевидно, строители придерживались первоначального рельефа почвы. У такого построения стены есть известные преимущества, так как упрощается движение по боевой площадке, сокращая число ступеней и лестниц. Кроме того, древнерусская безгвоздевая деревянная кровля с покрытием тесом, упертым в желоб «потока», и должна была иметь уклон вдоль сооружения. Наклонная кладка рядов кирпича применялась и в других русских крепостях, например в Смоленске. Она была широко распространена в XVII столетии при сооружении каменных зданий значительной протяженности. Продольный уклон по боевому ходу стен Нижегородского кремля во многом способствовал их сохранности, обеспечивая естественный сток воды. Это оказалось особенно важным после уничтожения в XVIII веке кровли над стенами.
Прямоугольные блоки кремлевских стен вытесывались из известковистого туфа, материала пористого, но хорошо сопротивляющегося ударам. Камень этот добывался по оврагам и береговым склонам Волги на расстоянии 40—100 км вниз по реке, между Работками и Лысковом, Могли его ломать и в месторождениях по Оке и Клязьме. Так, при ремонтных работах 1787 года бутовый камень привозили из села Подъяблонного нынешнего Богородского района.