Родился 20 января 1951 г. в селе Согратль Гунибского района Дагестанской АССР (ныне Республика Дагестан, РФ) в семье колхозников. Один из пяти детей. Младший брат Магомеда, Тайгиб Толбоев (род. 1955), в дальнейшем также стал летчиком-испытателем и был удостоен почетного звания Героя России.
Магомед Толбоев служил в рядах Советской армии с 1969 г. В 1973 г. окончил с отличием командный факультет Ейского высшего военного авиационного ордена Ленина училища летчиков им. дважды Героя Советского Союза В. М. Комарова (г. Ейск, Краснодарский край).
В 1970-х гг. служил летчиком в истребительной авиации Одесского военного округа, затем - в должности начальника парашютно-десантной подготовки истребительного авиационного полка в Группе советских войск в Германии (ГСВГ).
В 1979 г. окончил Высшую партийную школу ГСВГ. Год спустя уволился в запас в связи с направлением на учебу в школе летчиков-испытателей Летно-испытательного института (ЛИИ) им. М. М. Громова Министерства авиационной промышленности СССР (г. Жуковский Московской обл.). Окончил это учебное заведение в 1981 г.
В 1980-1994 гг. являлся летчиком-испытателем ЛИИ.
В 1984 г. стал выпускником вечернего отделения филиала Московского авиационного института им. Серго Орджоникидзе (МАИ) в Жуковском по специальности "инженер-системотехник".
В ходе работы в ЛИИ освоил и испытал более 50 типов и модификаций самолетов, в т. ч. МиГ-23М, МиГ-25, Миг-29, МиГ-31, Су-24, Су-27 и Су-30, а также сверхлегкие летательные аппараты "Эльф", МАИ", М-15, "Стаер" и др. Успешно произвел две аварийных посадки на самолетах с неработающими двигателями и одну посадку истребителя Су-27 с разрушенным хвостовым оперением. Несколько лет входил в состав сборной команды СССР по авиационному спорту.
В 1983-1994 гг. Магомед Толбоев состоял в отряде космонавтов ЛИИ, готовился к пилотируемым полетам на космическом корабле многоразового использования "Буран". Прошел курс в Центре подготовки летчиков-космонавтов им. Ю. А. Гагарина, выполнял подготовительные полеты. 15 ноября 1988 г. при возвращении "Бурана" из единственного автоматического орбитального полета Толбоев пилотировал самолет МиГ-25, с борта которого в Центр управления полетом передавались телевизионные кадры посадки космического корабля. После распада СССР программа пилотируемых миссий "Бурана" была закрыта.
Во время августовских событий 1991 г. Магомед Толбоев участвовал в защите Белого дома (Дом Советов РСФСР) в группе вице-президента РСФСР Александра Руцкого.
В декабре 1993 г. Толбоев был избран в Государственную думу 1-го созыва по Махачкалинскому одномандатному избирательному округу №11. В январе 1994 г. уволился из ЛИИ и ушел из отряда космонавтов в связи с переходом в Госдуму. Входил в депутатскую группу "Новая региональная политика", был заместителем председателя думского комитета по промышленности, строительству, транспорту и энергетике. В июле 1994 г. занял второе место на выборах председателя Госсовета - главы Республики Дагестан (голосование проводилось среди членов Конституционного собрания Республики Дагестан).
В 1994-1996 гг. учился в аспирантуре Российского университета дружбы народов (Москва) по специальности "История России". В 1995 г. защитил кандидатскую диссертацию на тему "Межнациональные отношения на Северном Кавказе, в Республике Дагестан в период 1985-1995 гг. и перспектива их развития". Доктор исторических наук (2006, тема диссертации в открытых источниках не публиковалась).
В период с июня 1996 по июнь 1998 г. занимал пост секретаря Совета безопасности Дагестана.
С 1997 г. по н. в. является почетным президентом ОАО "Авиасалон", компании-устроителя Международного авиационно-космического салона (МАКС, г. Жуковский).
В 1999-2000 гг. занимал должность командующего авиацией Московского округа внутренних войск Министерства внутренних дел (МВД) России, был главным инспектором авиации МВД России.
Живет и работает в г. Жуковском.
Генерал-майор в отставке. Летчик-испытатель I класса (1985).
Заслуженный летчик-испытатель РФ (1996). Почетный работник транспорта РФ (2011).
Магомед Толбоев удостоен почетного звания Героя Российской Федерации (1992, "за мужество и героизм, проявленные при испытаниях авиационной техники"). Награжден орденом Трудового Красного Знамени (1989, за работы по программе "Буран"), медалями, орденом "За заслуги перед Республикой Дагестан" (2011).
Женат. Супруга - Любовь Васильевна Толбоева (урожденная Кондратенко, род. 1946). Трое детей: Наталья (род. 1967, модельер), Руслан (род. 1974, предприниматель), Марина (род. 1986).
Магомед Толбоев увлекается волейболом, велоспортом, горными лыжами, парашютными прыжками в горах (выполнил более 1 тыс. 100 прыжков), парапланеризмом и др.