Отец, уроженец Перми, приехал по распределению из Пермской области в Волгоградскую, работал трактористом, развелся с женой, когда Павлу было два года, и уехал жить в Краснодарский край.
Мать — представитель местного старинного казачьего рода Щегольковых, работала директором детского сада, после его закрытия пошла в кочегары.
Согласно документам, родился на хуторе Большой Серафимовичского района Волгоградской области.
Детство провел на хуторе Горбатовский (в 25 км от Большого), население которого составляет около 600 человек. Жил в одноэтажном доме, обложенном белым кирпичом, с младшим братом, сестрой и матерью Валентиной Константиновной, 1957 года рождения.
Как рассказывает Лидия Уренева, классный руководитель Косолапова до 4 класса средней школы:
Надежда Прилепова, классный руководитель Косолапова в старших классах, вспоминает:
Наталья Уренева, одноклассница Павла, признаётся:
По словам директора Горбатовской средней школы Сергея Петрова в интервью «Независимой газете»:
По воспоминаниям преподавателей той же школы,
Как признается мать Павла обозревателю газеты «Известия» Дмитрию Соколову-Митричу:
По версии МВД, после окончания школы в 1997 году Косолапов поступил в Краснодарское высшее военное командное инженерное училище. По мнению школьных учителей Косолапова, «на это дело его муж родной сестры подбил».
В 1998 году училище было расформировано, часть курсантов, в том числе и Косолапова перевели в Ростовский военный институт ракетных войск им. Главного маршала артиллерии М. И. Неделина.
По воспоминаниям однокурсников, Косолапов любил экстрим — прыгал в реку с высоких мостов и в Краснодаре, и в Ростове. С людьми общался легко, однако лидером не был. Играл на гитаре. К деньгам относился неравнодушно: после занятий, в отличие от товарищей не развлекался, а подрабатывал.
Осенью 1999 года, за полгода до окончании учёбы, он написал рапорт с просьбой об отчислении после того как был уличён в воровстве денег у сокурсника. После отчисления из института проходил срочную службу в ракетных войсках в Ростовской области и в Чернышковском районе Волгоградской области.
В январе 2005 года бабушка Косолапова рассказала журналисту газеты «Известия»:
После демобилизации и возвращения в родной хутор Горбатовское, окончил курсы сварщиков. Однако по специальности не работал — в совхозе не платили денег. Павел зарабатывал покосами сена для скотины и вязал веники, которые мать и сестра продавали на рынке. В это же время сблизился со своими местными сверстниками Артуром Амиралиевым, Рустамом Джамурзаевым. Спустя некоторое время семьи Амиралиевых и Джамурзаевых перебрались на родину в Чечню. Вскоре после этого начались таинственные исчезновения Косолапова из родных краёв. По словам матери Косолапова:
В Чечне, по данным газеты «Время новостей», Косолапов воевал на стороне сепаратистов против федеральных войск. Там он прошёл подготовку под руководством арабских инструкторов в учебном центре «Кавказ» известного террориста Хаттаба в Сержень-юрте и принял ислам радикального толка, затем сам стал инструктором. Среди его учеников — граждане Казахстана Еркингали Тайжанов и Азамат Толеубай, ранее учившиеся в медресе в городе Бугуруслан Оренбургской области и воевавшие в отрядах Абу Умара и Абу Дзейта. Следует отметить, что имя Азамата Толеубая, уроженца поселка Карагайлы Карагандинской области, газета «Казахстанская правда» упоминала ещё в 2001 году в статье о молодых казахских парнях, якобы поступивших учиться в ваххабистский лагерь в Сержень-Юрте в марте 1999 года.
После принятия ислама Павел Косолапов взял себе новое имя — Мохаммед. На родину, в Волгоградскую область, он регулярно возвращался вплоть до 2004 года. Приезжал на автомобилях — сначала зелёной подержанной «ВАЗ 21099», потом на битой «Тойоте» с московскими номерами (на ней он проездил около трёх месяцев, пока окончательно не разбил в конце лета 2003 года, поехав с матерью на рынок в Ростовскую область), затем «ВАЗ 2109». По словам односельчан, пять раз в день молился, ругал и бил младшего брата Ивана за брань, выкуренную сигарету и употребление спиртных напитков.
В 2004 году официально работал в сельхозартели в Воронежской области. В том же году, по некоторым сведениям, приобрёл земельный участок в Краснодарском крае, где, по словам матери, он в своё время мечтал купить дом.
По версии правоохранительных органов, озвученной СМИ в 2005 году, группа Косолапова занималась подготовкой террористического акта в Московском метрополитене 6 февраля 2004 года. Куратором смертника Анзора Ижаева, осуществившего взрыв, унесший жизни 42 человек, якобы, был Косолапов.
МВД РФ объявило в розыск Косолапова и Тайжанова после серии терактов на автобусных остановках в Воронеже: 19 февраля 2004 года на остановке «Военный городок» на окраине города преступники установили сумку с бомбой, гвоздями и болтами. Однако благодаря ошибке при установке взрывного устройства ранения получили лишь два человека. 19 июля на остановке «НИИ генетики» произошёл другой взрыв мощностью 200 г в тротиловом эквиваленте, в результате которого от проникающих ранений грудной клетки погибла 26-летняя сотрудница Воронежской государственной сельхозакадемии Елена Фролова, ещё пять человек получили ранения различной степени тяжести. 26 июля на автобусной остановке на пересечении улиц 9 Января и Антонова-Овсиенко произошёл третий взрыв, однако в его момент на остановке никого не было.
Косолапов также подозревался в совершении этих терактов, поскольку накануне взрыва он проезжал там на машине, и даже был остановлен на посту ГАИ. Однако в 2006 году следствие выяснило, что за взрывами в Воронеже и в московском метро стоит другая террористическая группа, которую возглавлял этнический русский ваххабит Максим Понарьин. В 2007 году Максим Понарьин, а также Тамбий Хубиев и Мурад Шаваев были приговорены Мосгорсудом к пожизненному лишению свободы за участие в организации террористического акта в Московском метрополитене 2004 года.
В конце февраля 2004 года группа Косолапова-Тайжанова-Толеубая, по версии МВД, осуществила четыре взрыва магистрального газопровода около подмосковных Чехова, Подольска и Бронниц, а 15 марта — трёх опор ЛЭП у Симферопольского шоссе в Московской области.
В 2004 году, по данным правоохранительных органов, Косолапов вернулся на родину в Волгоградскую область, где познакомил своего ученика по лагерю в Сержень-Юрте Еркингали Тайжанова с местной жительницей, 18-летней беженкой из Армении Кристиной Мустафаевой, которая вышла за того замуж. Вскоре семья Тайжанова перебралась в Актюбинск, а затем в Самару, а 4 июня того же года тот осуществил взрыв на вещевом рынке в Самаре, в результате которого 11 человек погибли, а, по разным источникам, 38 или 71 были ранены.
3 сентября 2004 года ученик и приятель Косолапова Тайжанов был арестован в Казахстане за хранение наркотиков. На Тайжанова дала показания его супруга, которой тот ранее демонстрировал бомбу и признался что готовится её применить, а вскоре после взрыва показал 3000 евро, сообщив жене, что получил эти деньги за успешное проведение теракта. После того как Тайжанов узнал, что к нему в тюрьму едут следователи из России, он повесился в камере. По данным ФСБ РФ, Тайжанов планировал сделать жену, которая к тому моменту была от него беременной, террористкой-смертницей для исполнения террористического акта, который был запланирован в Москве на 27 сентября 2004 года. Сама Кристина Мустафаева заявила, что «Еркингали мне об этом никогда не говорил».
Другой ученик Косолапова Азамат Толеубай явился с повинной в МВД Казахстана, признавшись что был в Чечне и воевал на стороне сепаратистов, а также в том, что имел знакомство с Тайжановым. Однако свое причастие к терактам Толеубай отрицал. В июне 2005 года, по данным СМИ Казахстана, Толеубай был осужден судом в г. Актобе. В июле 2005 года Толеубай был выдан российским правоохранительным органам; по другим сведениям, он по-прежнему находится в Казахстане. По состоянию на октябрь 2009 года информацию о суде в России над Толеубаем обнаружить не удалось; последнее упоминание о нём в российских СМИ приходится на ноябрь 2007 года.
На имя Косолапова была оформлена съемная квартира в подмосковном городе Люберцы, где 18 марта 2004 года уборщицей риэлторской компании «Калита-град» была обнаружена сумка, набитая оружием. В девятиэтажном доме № 52 на улице Кирова в Люберцах на съемной квартире № 84 (по другим данным, в квартире № 84 в пятиэтажке по адресу ул. Кирова, 53) были обнаружены: 21 выстрел к ручному гранатомету РПГ-7, 2 гранаты Ф-1 и одна — РПГ-5, 19 электродетонаторов и 18 наручных часов Casio. Однако ни квартиранта, ни других лиц, проживавших в квартире, задержать не удалось.
13 августа 2007 года на перегоне Окуловка — Малая Вишера Октябрьской железной дороги в 21:38 по московскому времени в результате аварии с рельсов сошли электровоз и 12 вагонов поезда «Невский Экспресс». Были травмированы 60 человек, из которых 25 были доставлены в больницы. По официальной версии, причиной аварии стал подрыв железнодорожного полотна самодельным взрывным устройством мощностью 8-9 кг в тротиловом эквиваленте.
В 2007 году МВД РФ разослало ориентировку на Косолапова, объявленного в федеральный розыск:
Как сообщает газета «Коммерсантъ», по версии следствия, время, место, объект теракта и способ его реализации выбрал Павел Косолапов. Под видом туриста он приехал в Маловишерский район Новгородской области, лично осмотрел участок железнодорожного пути Санкт-Петербург—Москва на перегоне Бурга—Красненка и выбрал место для закладки взрывчатки неподалеку от моста через речку Чёрную; «гулявшего» по железнодорожным путям молодого человека приметили местные жители, которые в дальнейшем помогли составить его фоторобот. Тем временем безработный житель ингушского села Экажево, отец четверых детей Саланбек Дзахкиев подрядил своих земляков, братьев Хидриевых, на перевозку взрывчатки. Штукатур Макшарип и крановщик Амирхан якобы привезли её из Ингушетии в автомобиле ВАЗ-2109, который тоже видели свидетели. В Новгородской области они передали машину посреднику, причём с Саланбеком Дзахкиевым, по версии обвинения, контактировал только Макшарип Хидриев; Амирхан Хидриев просто согласился помочь брату перегнать «девятку» из Ингушетии в Новгородскую область.
В материале газеты «Известия» некоторые детали описаны по-другому: так, согласно ей, 9 килограммов гексогена были купленны Дзахкиевым в Москве и доставлены в Малую Вишеру Амирханом Хидриевым на принадлежащем ему автомобиле ВАЗ-2106. Кроме того, она отмечает, что братья Хидриевы до теракта промышляли автомобильными разбоями, пытками и побоями, заставляя владельцев дорогих машин переоформлять автомобиль на их имя.
По утверждениям газеты РБК daily, сославшейся на неназванный «источник в МВД», Косолапов также подозревается в подрыве «Невского экспресса» в 2009 году.