В 1959 г., когда Мобуту направили стажироваться в «Информконго» в Бельгию, Лумумба поручил новому соратнику представлять партию в Брюсселе. Здесь молодой человек получил достаточно солидное образование в Институте социальных исследований и в Институте журналистики. Он много читал и стал горячим поклонником де Голля, французской литературы и классической музыки. Вскоре, однако, стало известно, что стажер помимо этих увлечений имеет еще одно: Жозеф Дезире собирал сведения о конголезских студентах для бельгийской службы безопасности. Лумумба простил его, найдя очень простое оправдание: «Мобуту нуждался в деньгах, и я понимаю, почему он согласился, как многие, играть роль осведомителя. Теперь он у меня. А с этим покончено…»
Жозеф Дезире действительно не стал больше сотрудничать с бельгийцами, зато сыграл определенную роль в трагической судьбе своего партийного лидера, хотя всю жизнь отрицал это.
Вернувшись на родину, к этому моменту уже получившую независимость, Мобуту стал секретарем Кабинета Министров, во главе которого находился Патрис Лумумба, а позже в чине полковника возглавил штаб конголезской армии.
Лумумба придерживался курса на укрепление связей с СССР. Его противники внутри страны при поддержке западных служб безопасности организовали заговор против правительства. По приказу Мобуту из столицы страны Леопольдвиля были удалены верные премьеру войска. Там оставались только части, готовые принять участие в свержении правительства. В результате Лумумба был арестован, переправлен в сепаратистскую провинцию Катанга к главарю одной из племенных группировок Чомбе и там убит.
Власть в стране оказалась в руках президента Касавубу. Премьер-министром стал Чомбе, а Мобуту остался во главе вооруженных сил страны. Оставаясь в тени, он поддерживал связи с американскими спецслужбами. Известно, что по ночам глава штаба, получивший чин генерала, посещал американское посольство. Благодаря финансовой поддержке со стороны американских спецслужб он выплатил жалование военным, не получавшим его во времена Лумумбы. Это привлекло на сторону генерала большинство военных и помогло ему 25 ноября 1965 г. совершить военный переворот и захватить власть.
Став президентом страны, Мобуту первым делом позаботился об укреплении своего положения. Он оставил за собой должность главнокомандующего вооруженными силами и возглавил ряд ключевых министерств – иностранных дел, национальной обороны, безопасности территории и юстиции. В отличие от многих африканских тиранов новейшего времени генерал сделал ставку не на военную диктатуру, а на создание авторитарного президентского режима. Новая Конституция, принятая в июне 1966 г., узаконила президентское правление.