Лумумба надеялся поступить в недавно созданный Лованиумский университет в Леопольдвиле, но ему отказали, сославшись на то, что он женат; туда могли поступать только холостяки. Он был горько разочарован. Но в 1956 году он стал одним из немногих конголезцев, посетивших Бельгию, когда его выбрали для участия в учебной поездке.
В том же году Лумумба был арестован за хищение средств из почтового отделения. Он признался в краже, которую уже начал возмещать до того, как его поймали. Его приговорили к двум годам тюрьмы, но срок был заменен на двенадцать месяцев после того, как эволуи Стэнливиля собрали средства для выплаты оставшейся суммы. Они понимали его нужду в деньгах; хотя он выполнял ту же работу, что и белые, он не получал такой же зарплаты. Лумумба не терял времени даром, находясь в тюрьме. Он написал книгу Le Congo, terre d'avenir, est-il menacé? ("Конго, моя страна"), которая была опубликована в Брюсселе посмертно. Книга выступала против расовой дискриминации, но с позиции поддержки "цивилизаторской миссии", на которую претендовала Бельгия. Эта точка зрения была "диаметрально противоположна" тому дискурсу, который он развивал в течение последующих нескольких лет.
В 1957 году он переехал в Леопольдвиль, где работал на пивоварне Bracongo, производившей пиво Polar. Получив должность директора по рекламе, он ездил по стране, рекламируя пиво, что вызвало соперничество с пивоварней Bralima, которая производила пиво Primus. Во время этой "пивной войны", пишет Нзонгола-Нталаджа, "Лумумба оттачивал навыки публичных выступлений, которые так пригодились ему на политических митингах и собраниях".
Растущие надежды Лумумбы на политические перемены были подкреплены речью, произнесенной в Браззавиле 24 августа 1958 года Шарлем де Голлем, премьер-министром Франции, в которой он заявил о своей поддержке самоопределения французских колоний: "Тот, кто желает независимости, может получить ее немедленно". За рекой Конго в Бельгийском Конго, пишет историк Дэвид Ван Рейбрук, бельгийские семьи "подавились своим кофе", услышав речь по радио. Но в городе поднялось ликование.
Если такое могло произойти в Африке, управляемой Францией, думали Лумумба и многие другие конголезцы, то почему бы этому не произойти в Африке, управляемой Бельгией? Два дня спустя группа эволюционеров в Леопольдвиле передала генерал-губернатору Хендрику Корнелису подписанную петицию, в которой осуждался "анахронический политический режим" Конго и требовалась дата "полной независимости". Несколько недель спустя некоторые из тех, кто подписал петицию, основали новую политическую партию - Национальное конголезское движение. Ее председателем стал Лумумба.
28 сентября 1958 года де Голль объявил референдум на всех территориях Африки, находящихся под властью Франции, и спросил их, хотят ли они оставаться членами французского сообщества народов; альтернативой было самоуправление. Голосование, как их заверили, было свободным.
Лумумба верил, что де Голль говорит из лучших побуждений. Поэтому он был потрясен реакцией французов, когда Гвинея проголосовала против того, чтобы оставаться во французском сообществе, и за самоуправление - единственная французская колония в Африке, сделавшая это. Колония стала независимым государством 2 октября 1958 года. Французские граждане, проживавшие в Гвинее, разгневанные, массово покинули страну. Поскольку мало кто из гвинейского населения был обучен навыкам, необходимым для управления страной, Гвинея осталась без администраторов и технических специалистов. Не хватало и необходимого оборудования, поскольку французы забрали все, что могли унести, включая пишущие машинки. Франция была в ярости", - рассказывал американский офицер генеральной службы, работавший позднее в посольстве США в Гвинее:
Они вывели всех своих людей. Они вырвали электрические провода для уличного освещения, для жилых домов и офисов, сломали генераторы местной больницы, разгромили улицы - все, что только можно придумать, они сделали. Это было ужасно. Они сломали лифт в одном небоскребе, что было просто подло и злобно, и это было ужасно, и страна не смогла преодолеть это.
Это было очевидно. Я имею в виду дыры на улицах, разбитые фонари.... Они ломали вещи и краны.... Я имею в виду, назовите это, они сломали это. Они были полны решимости преподать этой стране урок, и им это удалось.