Лумумба с группой единомышленников основал осенью партию ""Национальное движение Конго"", которая выдвинула ясную и четкую программу — независимость страны без всяких оговорок, сплочение всех конголезских народностей и племен, создание единого государства, развитие братских связей с другими африканскими государствами.

Эта программа соответствовала интересам народных масс, и в партию стали вступать рабочие, крестьяне, мелкие чиновники, торговцы, интеллигенты; отделения ""Национального движения Конго"" возникли по всей стране. Но бельгийские власти и полиция, обеспокоенные популярностью и ростом влияния П. Лумумбы, стали преследовать его и угрожать арестом, в то же время стараясь подкупить его. Во время своего приезда в Конго сам бельгийский король Бодуэн беседовал с ним, обещая всяческие выгоды от сотрудничества с колониальной администрацией. Однако никакие обещания и угрозы не сломили воли и решимости П. Лумумбы, а между тем буря уже приближалась.

1959-й год начался в Конго с вооруженного выступления в городе Леопольдвиле африканских рабочих, поднявшихся на борьбу за независимость. Потом восстание перекинулось на другие районы страны, и лишь после жесточайшего террора бельгийским властям удалось ""восстановить порядок"". Но ненадолго… В конце октября 1959 года партия ""Национальное движение Конго"" устроила в Стэнливиле собрание с участием П. Лумумбы и других лидеров, но завершить его не удалось. Ворвались полицейские и, бросившись на П. Лумумбу, попытались схватить его, но участники собрания не допустили ареста. Тогда полиция открыла огонь, а когда дым рассеялся — на земле лежали несколько окровавленных тел африканцев.

Начавшиеся в Стэнливиле волнения вскоре охватили все Конго. Правительство Бельгии вынуждено было пойти на некоторые уступки, например, было объявлено о созыве в Брюсселе ""круглого стола"" с участием лидеров основных политических партий Конго. Конференцию, которая должна была объявить о сроке провозглашения независимости и структуре будущего государства, назначили на конец января 1960 года. Конечно, бельгийское правительство и не намеревалось предоставлять Конго подлинную независимость, а что касается П. Лумумбы, то его и партию ""Национальное движение Конго"" следовало отстранить от решения судьбы страны. За неделю до открытия конференции П. Лумумба был арестован ""за разжигание беспорядков"" и приговорен к шести месяцам тюремного заключения. Во избежание ""неожиданностей"" его отправили в тюрьму, расположенную в одном из самых глухих уголков Конго. Впоследствии П. Лумумба рассказывал, что по дороге жандармы всячески издевались над ним."

"Арест народного лидера вызвал взрыв негодования, и в стране развернулось движение за его освобождение.