Знакомство коренных народов России с мусульманской верой началось в первой половине VII века. Присоединение Дербента к Арабскому Халифату в 642–643 гг. ознаменовало начало первого этапа распространения ислама на Северном Кавказе. К началу VIII века власть Халифата окончательно утвердилась в Дербенте и его окрестностях, а в 733–734 гг. по приказу арабского полководца Масламы там была построена одна соборная и семь квартальных мечетей. Дербент, или Баб-эль-Абваб («Врата врат»), как его назвали арабы за важное стратегическое положение города, запиравшего выход из прикавказских степей на Ближний и Средний Восток, превратился в крупный центр распространения ислама. В городе поселились учёные и проповедники, которые вели проповедь среди местного населения. Сила оружия не могла обратить в ислам гордые и свободолюбивые кавказские народы, но слово и убеждения возымели действие на их сердца. Одними из первых ислам приняли лезгины, табасаранцы, цахуры. Процесс ознакомления жителей Северного Кавказа с новой религией растянулся на многие века, и это подтверждает тот факт, что кавказские народы не были обращены в ислам насильственным путём.
Упрочение торговых и культурных контактов со странами Ближнего Востока во второй половине X века привело к началу нового этапа распространения ислама в Дагестане. В этот период добившиеся фактической самостоятельности местные правители начали помогать распространению ислама для усиления собственной власти. В XI–XIII вв. мусульманами стали агулы и лакцы, а в XIV–XV вв. — ногайцы, арчинцы, кумыки, аварцы и другие народности. Однако окончательное утверждение ислама в восточных областях Северного Кавказа произошло лишь к началу XV века, когда ислам практически вытеснил другие религиозные верования. К тому периоду в Дагестане широко распространился суфизм, который начал проникать сюда с X–XI вв.
На территорию Центрального и Северо-Западного Кавказа ислам начинает проникать примерно с X–XI вв. Ещё ближе с исламом народы этого региона знакомятся во времена господства Золотой Орды, а после её падения мусульманскими проповедниками здесь становятся крымские татары, ногайцы и лишь изредка — турки. Кабардинцы сыграли большую роль в окончательном обращении в ислам части осетин, а также карачаевцев и балкарцев.
В Чечне и Ингушетии ислам распространился сравнительно поздно. В XV–XVI вв. благодаря деятельности мусульманских купцов и ремесленников из Дагестана он проникает в чеченские селения. В XVI в. здесь сложилась местная письменность, основанная на арабской графике. К XIX веку практически полностью приняли ислам ингуши. Последний ингушский жрец Элмарз-хаджи (1766–1923) принял ислам в 1873 г.
В горных селениях Северного Кавказа до сих пор высоко чтят память тех, кто, согласно преданиям, внес большой вклад в донесение Священного Корана до местных народов. Распространены предания о шейхе Абу Муслиме, проповедовавшем ислам в Дагестане, Гази-Каландаре из Сирии, обратившем в ислам лакцев, выходце из карачаевских князей шейхе Абдаллахе Бухарачи. Могилы десятков учёных и суфийских шейхов сохранены и особо почитаются последователями суфийских тарикатов.
По мере утверждения норм мусульманского права кавказские народы отходили от противоречащих Шариату обычаев, таких как захват имущества односельчан должника в обеспечение долга и лишение женщин наследства. Вместе с тем, ислам не вытеснил местные обычаи (адаты) полностью. На Северном Кавказе вплоть до начала XX в. параллельно существовал суд по адату и Шариату. По Шариату решались все дела, касающиеся религии, семейных отношений и наследования. Уголовные дела, общественные постановления и имущественные вопросы продолжали решаться по адатам.