Праздник впервые отмечался 15 сентября 2011 года. События, к которым приурочен этот праздник, произошли в 1741 году. В середине 18 века великий иранский полководец Надир-шах во главе хорошо вооруженной 100-тысячной армии двинулся на Кавказ. Он намеревался двумя огромными колоннами пройти через Дербент, Кайтаг и шамхальство Тарковское на столицу Мехтулинского ханства Дженгутай с одной стороны и через Шах-Даг, Могу-даре, Кази-Кумух и Хунзах — с другой, чтобы в результате покорить весь Дагестан. Поначалу захватнические планы Надир-шаха осуществлялись именно так, как он задумал. Огромная армия одерживала одну победу за другой, учиняя по пути расправу над населением. В результате, взяв по пути Кази-Кумух, войска шаха дошли до границ Андалала, 12 сентября 1741 года. Тем временем дагестанцы, не желавшие быть порабощенными иноземным шахом, стали объединяться в Андалальской долине — в районе предполагаемого сражения, в месте под названием «Хициб». Как повествует народный эпос Дагестана, на борьбу с врагом собрались добровольцы, которые вливались в боевые дружины, готовящиеся к тяжелому бою. Решающее сражение на территории Андалала продолжалось пять дней. Закаленные в боях опытные военачальники горских народов, воспользовавшись ослаблением оборонной силы шахских войск, повели своих воинов в наступление на врага. Героизм защитников родной земли стал массовым явлением. Так началось изгнание шаха с дагестанской земли. Андалальская победа упрочила геополитическое значение Дагестана как важного стратегического моста между Западом и Востоком, став убедительным свидетельством силы и мощи дагестанских народов. На III съезде народов Дагестана было принято решение ввести в республике новый праздник — День единства народов Дагестана. Указом президента Республики Дагестан от 6 июля 2011 года было постановлено отмечать его 15 сентября — в день, когда дагестанская армия повергла в бегство полчища Надир-шаха. Сегодня не столь важно, кто сыграл более значительную роль в решающих битвах; важно то, как почти триста лет назад, несмотря на разные языки, дагестанцы смогли выжить, лишь объединившись, как во все трудные времена они помогли друг другу в борьбе с врагом.
