Указ «О терпимости всех вероисповеданий» (1773), нацеленный именно на мусульман, предусматривал закрытие Новокрещенской конторы и провозглашал терпимость в отношении всех вероисповеданий; под действие его не попадали атеисты, вольнодумцы и еретики. Изданный в то время, когда Екатерина была занята покорением Крыма и причерноморских степей, он разрешал неограниченное строительство мечетей и свободу отправления культа для мусульман. Как указывает Роберт Крюс, вслед за этим Екатерина II приступила к реорганизации исламских религиозных институтов в Крыму и Среднем Поволжье, чтобы добиться от мусульман лояльности к царской власти. В 1784 году Россия установила контроль над духовенством Крыма (муфтиями и низшими духовными чинами), назначив на должности лиц, лояльных России, и отдав в их ведение всех мусульман полуострова и Причерноморья. В 1784 году аналогичная структура – Оренбургское магометанское духовное собрание – была создана для мусульман Среднего Поволжья, Сибири и крупнейших городов империи. Несмотря на название, он находилось в Уфе (в Оренбурге – лишь в течение краткого периода 1797–1802 годов). В него входили муфтии и кадии – мусульманские судьи.

Предполагалось, что данные институты будут назначать на местах имамов и учителей и следить за их деятельностью, отдавая предпочтение тем, кто получил образование внутри страны (в Казани и Оренбурге), а не мусульманам из-за рубежа, чья лояльность вызывала сомнения. Духовенство на местах должно было следить за религиозным образованием, разрешать конфликты, касавшиеся браков и разводов, и (самая чувствительная область) давать правильное толкование религиозных правил там, где существовало несколько интерпретаций – нередкий случай для ислама с его отсутствием центральной духовной власти. Оренбургские губернские власти наблюдали за деятельностью собрания. Первый муфтий, Мухаммеджан Хусаинов, был опытным политиком и верным слугой императрицы; он потребовал и получил от русских властей разнообразные льготы и привилегии, включая высокое жалованье и право на владение землей. Хусаинов возглавлял дипломатические миссии, направлявшиеся к сопредельным мусульманским народам (казахам, кабардинцам), подавлял оппозицию со стороны местного исламского духовенства, у которого новая структура вызывала беспокойство. После смерти Хусаинова российские власти постарались, чтобы муфтии не получали такой огромной власти. При Екатерине II государство покровительствовало своим мусульманским подданным: предоставляло средства на строительство некоторых мечетей в Среднем Поволжье, на Урале и в Сибири, платило жалованье не только муфтиям, но и другим мусульманским должностным лицам, наблюдало за постройкой мусульманских школ, издавало Коран и книги религиозного содержания в русских и татарских переводах, не давало православной церкви разворачивать миссионерскую деятельность среди мусульманского населения. Эта политика не менялась до 1820-х годов.