Когда Мухаммед прибыл из Мекки в Медину, он построил здесь мечеть. Она была сооружена из сырого кирпича и пальмовых деревьев и находилась рядом с его домом.
После кончины Мухаммеда похоронили в комнате его вдовы Айши. Позже рядом с ним похоронили его тестя и ближайшего сподвижника, первого праведного халифа Абу-Бакра. Второй халиф Омар расширил мечеть, и после своей смерти был похоронен рядом с могилами Мухаммеда и Абу-Бакра. Омар совершил много значительных дел, в числе которых было введение мусульманского летосчисления от хиджры (со времени переселения Мухаммеда из Мекки в Медину). Началом новой эры считается 1-й день 1-го месяца (мухаррама) — 16 июля 622 года. 1-го мухаррама родился и Шамиль.
Количество паломников, стремившихся посетить могилу Пророка, росло так стремительно, что мечеть перестраивалась и расширялась несколько раз. При халифе Малеке и сама могила Пророка стала частью вновь расширенной мечети. Правитель Османской империи султан Махмуд II возвел новый большой купол над могилой Мухаммеда, покрытый свинцом и выкрашенный в зеленый цвет. А в 1861 году султан Абдул-Меджид I полностью реконструировал и значительно расширил мечеть.
Исполненный благоговения, Шамиль вошел в мечеть и совершил приветственную молитву, встав между кафедрой и могилой Пророка, где, как говорил Мухаммед, находился один из райских садов. Затем он смиренно встал у золотой ограды, отделявшей усыпальницу Пророка, и произнес:
«Мир тебе, посланник Аллаха, Его милость и благословение!
Мир тебе, Пророк Аллаха!
Мир тебе, лучшему Его творению!
Мир тебе, господин посланников и имам богобоязненных!
Свидетельствую, что ты довел послание, оправдал доверие, давал искренние советы общине, беззаветно боролся во имя Аллаха!»
После этого Шамиль приветствовал Абу-Бакра, Омара и ангелов, которые, как считается, незримо здесь присутствуют.
В своих молитвах Шамиль благодарил Аллаха за дарованное ему счастье, просил о милости к своему народу и милосердии в Судный день.
Обосновавшись в Медине, Шамиль определил младшего сына в медресе при мечети, а дочь Нажабат выдал замуж за Дауда — сына Магомед-Амина.
Но вскоре на Шамиля обрушилось новое горе. 13 мая скончалась их единственная с Шуайнат дочь Сапият, которой было всего 16 лет. Она заболела еще в Мекке, сильно простудившись. Ее похоронили на кладбище Джаннат аль-Бакия, находившемся неподалеку от Мечети Пророка. Там были упокоены жена Мухаммеда, члены его семьи и еще более 10 тысяч сподвижников Пророка.
Через несколько месяцев скончалась и дочь Шамиля Патимат.
С тех пор глубокая печаль уже не покидала сердце имама. Слабело и его здоровье. Порой он даже не мог встать и вынужден был молиться лежа.
Жены умоляли Шамиля переселиться в Стамбул, где климат был более мягким. Но Шамиль молил Аллаха о другом: «О владыка, о мой господин, если мое намерение, мои старания, усилия и мое сражение за веру перед тобой чисты и находят одобрение у твоего посланца, то не удаляй меня от соседства с твоим Пророком, дай мне умереть в храме твоего любимца, покажи мне его лицо, награди меня его любовью, воскреси меня среди постоянно находящихся при нем и не лишай меня его заступничества».
Богуславский, поддерживавший с Шамилем переписку, теперь писал начальству: «Шамиль, уехавший в отпуск с положительными намерениями вернуться опять в Россию, переменил свои мысли и не думает более возвратиться. Этому может быть единственная причина — материальная для него невозможность предпринять обратное путешествие, долгое и трудное, которое ему уже не по силам».
В августе 1870 года сыновья Шамиля получили письмо, в котором отец сообщал о кончине их сестер и о том, что он болен и желал бы увидеть перед смертью детей своих. Братья тут же обратились к военному министру Милютину с просьбой отпустить их на свидание с больным отцом. Министр отнесся к просьбе сочувственно и ходатайствовал перед императором об удовлетворении просьбы детей Шамиля.
Император согласился, но с условием, что в Аравию, в 6-месячный отпуск, поедет лишь Гази-Магомед, а Магомед-Шапи, как состоящий на военной службе, останется в России. Но бюрократические проволочки привели к тому, что Гази-Магомед потерял драгоценное время и смог выехать лишь 23 декабря, оставив в Киеве свою вторую жену Хабибат, на которой женился еще в Калуге, и маленькую дочь.
Путь его лежал через Стамбул, и весть о прибытии наследника имама взбудоражила кавказских мухаджиров. Многие полагали, что Гази-Магомед сделается их новым вождем. Турецкие власти тоже старались вовлечь Гази-Магомеда в орбиту своих интересов.