Родился 3 (16) октября 1910 в ауле № 16 ныне Макатского района Атырауской области Казахстана в семье рабочего. Казах. В 1932 году окончил рабфак в Алма-Ате. Работал старшим секретарём, следователем Гурьевской областной, затем городской прокуратуры Казахской ССР.
В Красную Армию призван в 1941 году Макатским райвоенкоматом Гурьевской области Казахской ССР. Участник Великой Отечественной войны с июня 1941 года. Член ВКП(б) с 1942 года. В 1942 году окончил Военно-политическое училище в городе Елабуга (Татарстан), в 1944 году — Московское пулемётное училище.
Командир стрелкового взвода 538-го стрелкового полка (120-я стрелковая Гатчинская Краснознамённая дивизия, 21-я армия, 1-й Украинский фронт) младший лейтенант Муса Баймуханов в январе 1945 года по тонкому льду первым преодолел реку Одер в районе Оппельна (ныне — Ополе, Польша).
Воины-пехотинцы под командованием младшего лейтенанта Баймуханов вступили в бой с противником на левом берегу Одера, чем способствовали быстрой переправе подразделений 538-го стрелкового полка.
Ворвавшись в деревню Одерфельде, вверенный офицеру Баймуханову взвод отразил многочисленные вражеские контратаки. В этом бою взводом было уничтожено двадцать пять гитлеровских солдат и офицеров, а командир взвода Баймуханов лично истребил девять фашистов.
Муса Баймуханов пал смертью храбрых в бою 18 марта 1945 года. Похоронен под польским городом Бяла «в 200 метрах северо-западнее города Зюльц, близ города Оппельн», как сообщалось в донесении о безвозвратных потерях офицерского состава 120-й стрелковой дивизии за период с 18 по 31 марта 1945 года.
Указом Президиума Верховного Совета СССР от 10 апреля 1945 года за образцовое выполнение боевых заданий командования на фронте борьбы с немецко-фашистскими захватчиками и проявленные при этом мужество и героизм младшему лейтенанту Баймуханову Мусе Баймухановичу посмертно присвоено звание Героя Советского Союза.
В районном центре Атырауской области Республики Казахстан — посёлке Макат — установлен бюст Героя, его именем названа одна из улиц этого посёлка.