В 2002 г. в Москве открылось представительство Управления мусульман Кавказа, которому были переданы помещения, в советское время занимаемые Отделом международных связей мусульманских организаций СССР. При этом Аллахшукюр Паша- заде особо отметил, что эти помещения были переданы ему при содействии Святейшего Патриарха Московского и всея Руси Алексия II⁸⁸.

В 1997 г. при активном участии шейх-уль-ислама Аллахшукюра Паша-заде был воссоздан Отдел международных связей мусульманских организаций СССР, зарегистрированный под названием «Международной исламской миссии» (МИМ). Президентом и вице-президентом МИМ стали близкие сподвижники шейх- уль-ислама Тагир Халилов и Сабир Мамедов, курировавшие вопросы внешней исламской дипломатии еще в советский период. Пост исполнительного директора МИМа занял первый муфтий Кабардино-Балкарской Республики Шафиг Пшихачев.

Главными целями МИМа были следующие: противодействие экстремизму и терроризму; укрепление дружбы между народами независимо от вероисповедания и расовой принадлежности; распространение народной дипломатии; воспитание патриотизма у подрастающего поколения и, что особенно важно — укрепление авторитета России на мировой арене⁸⁹.

Особое внимание новая структура стала уделять восстановлению разрушенных связей между мусульманами СНГ, в первую очередь — с мусульманами Средней Азии. Представители МИМ сумели наладить постоянные контакты с ведущими исламскими учебными заведениями Узбекистана, муфтиями Казахстана, Киргизии, Таджикистана, Украины и других республик СНГ. Со временем эта работа создала подходящую почву для объединения мусульман СНГ в постоянно действующую структуру.

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

В 2006 г. МИМ выступила соучредителем Фонда исламской культуры, науки и образования, после чего ее деятельность резко активизировалась. В мае того же года МИМ совместно с Управлением мусульман Кавказа выступила инициатором создания Верховного совета мусульман Кавказа, в первую очередь призванного оптимизировать борьбу с экстремизмом. Главным координатором новой организации стал президент МИМ Тагир Халилов⁹⁰.

С 2006 по 2009 гг. МИМ стала инициатором проведения ряда конференций, оказала помощь школам-интернатам для детей-сирот и приняла активное участие в подготовке документального фильма об экспансии исламистов на Кавказа в начале 90-х гг., который был показан по Первому каналу российского телевидения в июне 2008 г.⁹¹