Лумумба так ни о чем и не договорился с лидерами китавалы. Он не смог убедить их в том, что сектантское движение в силу его узости и ограниченности не в состоянии решить общеконголезских проблем. Нужно мощное национальное течение, которое бы вобрало в себя отделения в провинциях, городах и деревнях. Как найти слово, объединяющее всех конголезцев независимо от религиозных и племенных различий?
Лумумба основывает газету «Ухуру» («Свобода»). Материалы публиковались в ней на двух языках — французском для интеллигенции, и для сельского населения провинции — на суахили. Он начинает издавать еженедельник «Индепенданс». По инициативе Лумумбы создается Национальный союз конголезских трудящихся. В 1955 году он избирается председателем провинциальной секции профсоюза служащих-африканцев. Он писал статьи для газеты, тираж которой все время возрастал, сочинял стихи и отправлял их то в Брюссель, то в Париж, выступал на митингах и собраниях и в городе, и за его пределами.
В 1956 году Лумумба с группой конголезцев побывал в Брюсселе: перед Всемирной выставкой, открытие которой готовилось в бельгийской столице, шла усиленная идеологическая обработка африканцев. Лумумбу приглашали министры, лидеры бельгийских политических партий. Ему предлагали высокий пост в министерстве колоний. Отказался. Ну, а согласен ли он быть бургомистром Леопольдвиля? Нет, и на это не согласен. Тогда колониальные власти испробовали другой метод: Лумумбу арестовали. Он отбыл шесть месяцев предварительного Заключения. Первое знакомство с конголезской тюрьмой состоялось. Выйдя из заключения, Лумумба собирает своих единомышленников и обсуждает с ними устав новой политической партии: Конголезское национальное движение (НДК) заявило о себе в октябре 1958 года. Он все реже встречается с либералами и социалистами: в Ки-зангани белые поселенцы создали либеральную партию и социально-христианскую. И в ту и в другую входило несколько африканцев — преимущественно эволюэ.
После возвращения из Аккры Лумумба вместе с другими конголезскими делегатами опубликовал манифест с требованием независимости для Конго уже в 1960 году. С этого момента началась колониальная кампания против «учеников Нкрумы и Секу Туре», против «конголезских коммунистов». Лумумба несколько раз выступал в Леопольдвиле: нигде до этого он не собирал такой большой аудитории. Он проводил мысль о едином и неделимом Конго. Касавубу поддерживал эти требования, иногда сопровождая их оговорками насчет того, что относительно незначительных расхождений во взглядах партий можно будет легко прийти к соглашению после независимости. На митинге в общине Калуму Лумумба заявил:
— Бельгийский колониальный режим переживает в настоящий момент самый острый кризис за все время своего существования. Бельгия не в состоянии справиться с национальным движением миллионов конголезцев. Ее африканская политика зашла в тупик. В одном Леопольдвиле насчитывается около двадцати пяти тысяч безработных. Они не получают никакого пособия. Правда, сердобольная администрация находит выход из положения в том, что за свой счет — подумайте: какое разоренье! — покупает билеты этим нищим людям, чтобы они отправились в провинцию. А что ждет их на родине? Конголезца изгоняют из родной столицы. Киншасу хотят превратить в город белых поселенцев. Оказывается, мы с вами мешаем благополучию господ капиталистов. Что нам делать в такой ситуации? Выход в борьбе, дорогие соотечественники! Высылка африканцев — это провокация с негодными средствами и целями. Полицейские сейчас заняты переписью иноплеменных, они пока что оставляют в покое жителей Баконго. Таким образом, бельгийцы намерены поссорить национальности нашей страны и учинить межплеменную резню. Братья, держитесь вместе! Все мы — сыны и дочери единого Конго. Перед нами один враг. Кто из вас поверит, что колонизаторы лучше относятся к народу баконго, чем к другим национальностям?
Полицейские схватили Лумумбу, отвезли в участок, но вскоре выпустили. Репрессии властей усиливались. Единственная конголезская газета, выходящая в Леопольдвиле под названием «Конго», была запрещена. Полицейские рыскали в африканских кварталах.
Четвертого января 1959 года в квартале Фонкобель была подожжена полицейская автомашина. В этом квартале находились торговые дома португальских и греческих бизнесменов. Начались погромы. Народ вышел из-под контроля: прибывшие полицейские были разогнаны толпой. Усилия абаковцев, которые пытались сдержать разъяренную толпу, ни к чему не привели. Конголезцы поджигали дома всех европейцев, грабили магазины. На подавление стихийно вспыхнувшего мятежа прибыли воинские части из Тиесвиля и военной базы Камина. Пролилась кровь. Несколько африканцев было убито. Много ранено. Броневики мяли африканские хижины, прочесывали улицы из пулеметов. Через несколько дней с восстанием в Леопольдвиле было покончено. В Брюсселе бельгийский монарх выступил по радио с заявлением. «Ныне, — говорил король Бодуэн, — мы полны решимости вести конголезское население в условиях процветания и мира к независимости, избегая при этом как пагубных проволочек, так и неразумной поспешности».