Вместе с тем к XV в. постепенно восстанавливает силы Табасаран, разделившийся на северное майсумство и южный казият. В Нагорном Дагестане появляются новые крепкие мусульманские государства – Аварское нуцальство, Кайтагское уцмийство, Казикумухское шамхальство, Дербентский эмират. Первое возникло на развалинах Серира и охватывало земли современной Аварии. Кайтаг и Казикумух (на месте Гумика) поделили между собой не только горы, но и плоскость Центрального и Северного Дагестана. Дербент контролировал равнину Юждага. Наиболее сильным государством стало Казикумухское шамхальство, заставлявшее остальные владения платить себе дань. Правившие в Казикумухе, Кайтаге и Аварии наследные князья возводили свои роды к потомкам пророка Мухаммеда, пришедшим на Кавказ с легендарным арабским полководцем Абу-Муслимом. Арабские генеалогии этих владык в большинстве своем фиктивные. О них нет известий в раннесредневековых источниках, а сами титулы – уцмий, нуцал, кроме шамхала, майсум – появились только в послемонгольское время.

Во внутренних районах Нагорного Дагестана и Чечни началось усиление сельской общины или джамаата. К XV–XVI вв. тут появилось несколько десятков союзов сельских общин, такие, как Акуша-Дарго, Цудахар, Салатавия, Ункратль (аварск. ункъ ракь – “Четырехмиземье”), Нохчмахчкой, Галгай и др. По традиции, идущей от дореволюционных ученых, в литературе такие союзы обычно называют “вольными обществами”. Не все из них были самостоятельны. Большинство дагестанских “вольных обществ” зависело от казикумухских шамхалов, другие – от кайтагских уцмиев или аварских нуцалов. Они выплачивали им ежегодный поземельный налог (харадж) и выставляли ополчение из всех взрослых мужчин в войско своих сюзеренов на случай войны. Укрепление общины и некоторая стабилизация политической обстановки происходили на фоне подъема экономики региона. В эту эпоху восстанавливается волго-каспийская торговля. Растут старые и появляются десятки новых селений в горах и на плоскости.

Начиная с XIV–XV вв. внутреннее устройство местного мусульманского общества хорошо известно по источникам. В позднее Средневековье оно делилось на ряд сословий. Основное население региона было представлено сословием узденей. Как и на Северо-Западном Кавказе, в Дагестане, Чечне и Ингушетии этим тюркским словом называли не только горских дворян, но и свободных общинников. Они делились на богатых, средних и бедных; родовую знать и менее родовитых; коренных и пришлых и т. д. Все уздени участвовали в народном собрании общины, служили в ополчении своих джамаатов. В районах, зависевших от шамхалов, нуцалов или более мелких князей (беков), предводителями ополчений выступали ханы. Последние стояли на самом верху сословной иерархии. Беки и потомки от браков беков с узденями, носившие имя чанков, считались ниже их по положению. В период наибольшего могущества Казикумухского шамхальства беки и чанки из Казикумуха проникли в ряд высокогорных джамаатов. Только в Северо-Западном Дагестане, Чечне и Ингушетии так и не сложилось ханско-бекского сословия.

В положении крепостных пребывали райяты, прикрепленные к землям, находившимся в частной собственности (мульк) или пожалованным на условии несения военной службы бекам и служилым узденям (икта). На плоскости на землях ханов находились целые райятские поселения. В приморском Дагестане весь тюркский народ терекеме считался райатами кумыкских беков. В горах Чечни и Северного Дагестана райатов было немного. Низшую ступень сословной иерархии занимали рабы (лаги, кули, караваши). Они принадлежали отдельным кланам (тухумам, тейпам). Источниками формирования лагского сословия были военные походы и работорговля на невольничьих рынках. В высокогорной части региона рабов было немного. Зато в центральной, предгорной Аварии, в Лакии, у даргинцев и кумыков лагское сословие занимало видное место и играло большую роль в хозяйственной жизни общины. Описанное выше социально-политическое устройство региона с незначительными изменениями просуществовало до присоединения региона к России.