С 1680-х годов и до конца первой четверти XVIII века по Среднему Поволжью, Башкирии, калмыцким землям прокатились две волны обращения в православие: в первом случае крещение было принудительным и, более того, насильственным, во время второй волны (1720-е годы) средствами служили религиозное образование и проповедь. Землевладельцев заставляли креститься под угрозой лишения собственности и перевода в крестьяне. Одновременно насильственное крещение совершалось над тысячами анимистов (остяками, вогулами) в Сибири и мусульманами-татарами; в 1720-х годах тобольский архиепископ с особым усердием крестил местных жителей, мусульман и немусульман, и приказал снести 25 мечетей в одном только Тобольске, что вызвало недовольство в Сибирском приказе. Между тем восстания башкир на Южном Урале (1681–1683, 1704–1711) предотвратили принятие наиболее жестких мер. Так или иначе, как замечает Майкл Ходарковский, христианизация «шла небыстро» и, как правило, была поверхностной.
Православная церковь действовала в этом отношении неэффективно, так и не создав, в отличие от католиков, протестантов или буддистов, миссионерских обществ, состоявших из священников или монахов. Она не тратила ни сил, ни средств на обучение священнослужителей местным языкам, перевод вероучительных и богослужебных текстов, устройство школ, монастырей, приходов. Обращение всегда совершалось совместными усилиями церкви и государства, обычно при помощи материальных стимулов или силы, а не путем терпеливого проповедничества и внушения новокрещеным понятия о вере. Тем не менее, в 1740-х годах государство вновь предприняло кампании по обращению в этих же землях, чтобы ускорить их ассимиляцию. Башкирское восстание 1735–1740 годов, во время которого русские войска уничтожили 12–14 % всего башкирского населения и разрушили множество мечетей, побудило власти действовать более настойчиво. В 1740 году была создана Контора новокрещенских дел (Новокрещенская контора), целью которой было обращать в православие жителей Среднего и Нижнего Поволжья и Урала, особенно тех, кто исповедовал анимизм и ислам. Контора прибегала к материальным стимулам (освобождение на три года от подушной подати и рекрутской повинности) и насильственным действиям (разрушив более 400 из 518 мечетей в Казанской провинции). Ее действия встретили упорное сопротивление, и, несмотря на насильственное обращение приблизительно 400 тысяч представителей финно-угорских народностей и 7 тысяч татар, победа оказалась бесплодной. Православная церковь не дала своим новым членам надлежащего образования и приходской организации. Положение в Башкирии оставалось настолько неустойчивым, что местный губернатор не допустил туда сотрудников Конторы. После очередного восстания башкир (1756) государство в какой-то мере отступило, разрешив строить в Среднем и Нижнем Поволжье и на Урале новые мечети общинам, где насчитывалось более 200 мужчин. Как бы то ни было, В. М. Кабузан заключает, что прирост числа православных на вышеуказанных землях (Казанская, Нижегородская, Воронежская и Оренбургская губернии) происходил в основном за счет анимистов. Мусульмане же оказывали сопротивление, доля их в общей численности населения (около 12 %) не менялась на протяжении первой половины столетия.
Указ «О терпимости всех вероисповеданий» (1773), нацеленный именно на мусульман, предусматривал закрытие Новокрещенской конторы и провозглашал терпимость в отношении всех вероисповеданий; под действие его не попадали атеисты, вольнодумцы и еретики. Изданный в то время, когда Екатерина была занята покорением Крыма и причерноморских степей, он разрешал неограниченное строительство мечетей и свободу отправления культа для мусульман. Как указывает Роберт Крюс, вслед за этим Екатерина II приступила к реорганизации исламских религиозных институтов в Крыму и Среднем Поволжье, чтобы добиться от мусульман лояльности к царской власти. В 1784 году Россия установила контроль над духовенством Крыма (муфтиями и низшими духовными чинами), назначив на должности лиц, лояльных России, и отдав в их ведение всех мусульман полуострова и Причерноморья. В 1784 году аналогичная структура – Оренбургское магометанское духовное собрание – была создана для мусульман Среднего Поволжья, Сибири и крупнейших городов империи. Несмотря на название, он находилось в Уфе (в Оренбурге – лишь в течение краткого периода 1797–1802 годов). В него входили муфтии и кадии – мусульманские судьи.