История образования селения Кудали уходит своими корнями в глубокую древность. Есть предположение, что селение образовалось от слияния более мелких близлежащих поселений. Примерная дата основания собственно аула Кудали точно не установлена. Из рассказов старожил Кудали известно, что аул не раз подвергался разрушению. Его отстраивали семь раз. Возможно, это было связано с тем, что местное население не желало отказываться от своих прежних языческих и христианских верований. За подобную строптивость, как показывает историческая практика, аулы обычно разрушали и переселяли на другое место. И здесь, первым делом строили мечеть.

Сохранившихся исторических памятников в селении Кудали очень мало. Одним из самых примечательных является древняя мечеть, на стенах которой сохранились строительные надписи XIX в. на арабском языке. По их данным мечеть основательно реставрировали три раза: в 1813, 1865 и 1889 годах.

В одном из списков средневековой рукописи  "Тарих Дагестан" Мухаммадрафи (XIV-XVI вв.), содержится информация о том, что союз сельских обществ Андалал получил свое название в результате добровольного принятия ислама. Прежде же союз назывался Вицху и объединял селения Кудали, Чох, Согратль, Обох, Мегеб, Гамсутль, Ругуджа,  Кегер, Салта, Корода, Гуниб, Хоточ, Гонода, Хиндах.¹  Практически в каждом из этих селений известны яркие памятники христианской культуры.² По мнению известного историка и археолога Д.М. Атаева, христианство сохраняло  свои позиции в этом районе вплоть до XIV-XV вв. ³

В раннесредневековых  владениях Нагорного Дагестана,  царствах Гумик (лакские земли) и Сарир (аварские земли),  исповедывали христианство. Ныне об этом свидетельствуют многочисленные археологические памятники, об этом писал еще в 956 году и арабский историограф Масуди. На землях  Андалала, одного из мощных аварских союзов сельских общин Нагорного Дагестана, расположенном между христианскими владениями Гумик и Сарир, в этот период так же исповедывали христианство. 

В  1971 г. в окрестностях с. Кудали, в местности Агада, школьными краеведами было обнаружено древнее погребение и, как выяснили позже ученые-исследователи - христианское. На этом месте, в средневековый период здесь бытовала небольшая крепость (ХI-ХIII вв.).

При осмотре террасы перед небольшой возвышенностью внимание исследователей привлекли развалины камня и остатки стен помещений, находящихся рядом с могильником. Ближайшее знакомство с ними не оставляло сомнения в том, что здесь в древности бытовала небольшая, но хорошо укрепленная крепость. Она располагалась на участке, надежно защищенном с трех сторон обрывистыми склонами глубокого оврага и берегом реки. По всей окружности крепости прослеживались остатки оборонительных стен. Наиболее возвышенную и хорошо укрепленную часть крепости занимала цитадель неправильных очертаний.

Обломки красноглиняных горшков с заштрихованной поверхностью, собранные на территории крепости, а также особенности самых крепостных сооружений, характерных для периода становления феодальных отношений Дагестана, дали возможность установить время бытования крепости ХI- ХIII вв.  Исследование могильника подтвердило это предположение.

Могила представляла собой гробницу длиной в два метра, сложенную из камней. Сверху гробницу перекрывали  довольно массивные плиты, уложенные поперек его стенок. На дне гробницы был расчищен костяк молодой женщины. Она лежала на спине, с уклоном на правый бок, головой на северо-запад. Руки ее были вытянуты вдоль туловища, колени сходились в суставах, ступни  были вместе.

У головы, справа поставлен небольшой красноглиняный кувшин, а с левой стороны находилась маленькая миска, покрытая зеленой поливой. Около правой руки стоял миниатюрный красноглиняный туалетный сосудик. На обе руки погребенной были надеты бронзовые браслеты, а на палец правой руки - бронзовое кольцо. Около головы мы нашли 2 бронзовые инкрустированные подвески тонкой ювелирной работы. Шею и грудь погребенной украшало ожерелье из 53 разноцветных бус, изготовленных из пасты, сердолика, фаянса, бронзы. Там же были 33 так называемые раковины кауры, 1 перламутровая подвеска, 6 бронзовых ажурных подвесок, 2 маленькие морские ракушки, еще 2 бронзовые проволочные подвески, прикреплявшиеся к одежде. На груди был обнаружен бронзовый нательный крест (на нем сильно схематизированное изображение распятия Христа, концы креста имеют форму трилистника). В ногах лежало железное шило и еще какая-то железная поделка.⁴ Обряд погребения был определен исследователями  как смешанный, языческо-христианский. По рассказам стариков, до утверждения ислама, у кудалинцев действительно существовали языческие погребальные обычаи, в частности - хоронить вместе с умершим мужчиной и его лошадь. Последний рассказ неожиданно подтвердился, когда в 1976 году   в местности хутора Загира Чумагомедова  открылась старинная могила. 

Женщина, погребенная в агадинской гробнице, судя по сопровождавшему ее инвентарю, принадлежала к довольно зажиточной семье. Особенно интересной находкой Кудалинского могильника был нательный крест. Когда кудалинцы узнали, что их древние предки были "неверными" и исповедовали христианство, они очень смутились. Хотя всем давно было известно, что в окрестностях аула, в местности "БагIаралъул бакъдаб" на самой вершине холма "Гъал", "Аналъул гухI" (буквально "Воскресный холм"), сохранился фундамент христианского храма.

Инвентарь могильника позволил установить дату ее погребения. Сравнение материала из Кудалинского могильника показало, что он сходен с материалами Галлинского, Ирибского, Цурибского и Ортоколинского могильников, датируемых ХI-ХIII вв.⁵  Возможно именно к этому периоду и относится образование аула Кудали. К XIII-XIV векам в истории Аварии принято относить возникновение крупных сел в результате слияния нескольких мелких поселений. Об этом свидетельствуют многочисленный подъемный археологический материал, наличие и поныне вблизи большинства современных сел развалин заброшенных поселений, собственно легенды и предания об их объединении в одно целое.⁶ 

До нас дошли только предания, cогласно которым  кудалинцы жили в небольших поселениях Сидохъ, ЦIад-гьарихъ, Ухичурилъ, КIибичIараб-ганчихъ, Къавохъ, Рохьдол-къавохъ, Гьунабазул-болола, Кудала-маарда и др. Руины некоторых из них - Сидохъ, Къавохъ, ЦIад-гьарихъ, Ухичур, Кудала-маарда, КIибичIараб ганчIихъ, Агьадиб, Гьунабазул болола можно увидеть и поныне.

В результате их слияния образовалось одно крупное селение Кудали - от слова "КIудаб", т.е. с аварского яз.  "большой", "великий". Одной из причин объединения старожилы аула объясняли тем, что поселения объединились с целью самообороны против частых и внезапных набегов со стороны неспокойных соседей обществ Акуша-Дарго.

О том, что жители новообразованного аула действительно были вынуждены защищаться, говорит и его месторасположение - на вершине обрывистой горы, и несколько старинных боевых  башен.  

В Кудали было известно  4 башни. Одна  из них находилась между домами Чакарил Магома и Алиева Абдусамада.  Она называлась Арахской башней. Две другие башни были расположены в квартале "Хьундаб": одна к востоку от дома Шарапилова Магомеда, другая - между домами Гусейналова Дибирали и Махмутилова. В 90-х годах прошлого века была разрушена последняя и самая высокая башня, расположенная во дворе  Алиева Сааду.  По другим рассказам, эта башня была расположена прямо во дворе Сибугева Хажимухамада, между Джума-мечетью и большим годеканом.

Башни четырехугольной формы, слегка суженные кверху,  были сложены из местного бутового камня и  имели 4-5 этажей. Из нижнего помещения в верхние этажи поднимались по приставной крутой деревянной лестнице. В стенах башен местами были выложены каменные плиты с орнаментом и арабской письменностью. В Арахской башне были известны  изображения лошадей, крестов и сцена охоты на оленя из лука. 

Джума мечеть, выстроенная в самом центре исторического аула Кудали, построена, по рассказам старожилов, во время исламизации аула легендарным Абулмуслимом-шейхом.⁷ Примечательно, что преобразование аула и здесь традиционно связывают с арабским полководцем, миссионером Абу-Муслимом, которому средневековые дагестанские хроники  и устные предания приписывают распространение ислама в Дагестане. По мнению исследователей, сравнительный анализ хроник, посвященных деяниям Абу-Муслима, памятных записей и устных преданий позволяет предположить, что он представляет собой обобщенный образ героя исламизатора, возникший благодаря слиянию воедино образов нескольких исламских миссионеров арабского, тюркского, иранского и местного происхождения, действовавших в Дагестане в VIII-XVI вв.⁸

Возможно, ислам в кудалинских землях утвердился несколько раннее, чем в окрестных аулах Хунзаха. По преданию, когда арабы бились с батлаичцами, в арабский лагерь явился некий "нусил-бетер" - сотник народного войска "бо" из сел. Кудали. Он предложил Абулмуслиму свои услуги с целью помочь завоевать Батлаич, но попросил за это право обложить батлаичцев данью: по мерке зерна с каждого двора. Абулмуслим согласился, и Батлаич был   захвачен. Дань же эта, по преданию, взималась очень долго. ⁹

Проникновение ислама в Андалал традиционно связывают с возрастающим влиянием Кумуха. Возникшее на рубеже XI-XII вв. в процессе распространения ислама в Дагестане, сильное мусульманское государство - Казикумухское шамхальство, начинает активно поглощать под флагом газийской исламизации земли в бассейне Аварского и Кара-Койсу. Известно, что распространяемый из Кумуха ислам в 1435 г. утвердился в Карахе, а в 1475 г. в Гидатле. Андалал, географически расположен примерно между двумя этими обществами - и, т. о. время провозглашения здесь ислама господствующей религией возможно оказывается между двумя этими датами,  т. е. 80-е годы XIV в. - середина XV века.

Многочисленные местные предания свидетельствуют о сопротивлении населения Андалала новой религии (сс. Согратль, Чох, Ругуджа и др.) Видимо, кудалинцы в их числе не составляли исключения.

По преданиям, у кудалинцев издавна был свой правитель - хан.   Резиденция  последнего кудалинского хана находилась в центре старой части аула Кудали. До сих пор в окрестностях аула сохранились названия местностей, связанных с пребыванием здесь хана: "Хан рештIинеб гухI"   - "Холм, где отдыхал и останавливал хан",  "Ханасул рохь"  - "Ханский лес". А здание у большого годекана, там, где сейчас стоит дом Азиловых., известно под названием  "Ханасул рукъ"  - "Ханский дом".