Już wówczas przyszły premier potrafił mówić w języku tetela, francuskim, suahili, lingala i luba. Po powrocie do ojczyzny w styczniu 1959 zastały go antykolonialne zamieszki. Wystąpienia spacyfikowały służby bezpieczeństwa, zabijając 200 osób. Po aresztowaniach wśród działaczy afrykańskich Lumumba chwilowo zbiegł do sąsiedniego Konga Brazzaville.
W październiku 1959 zorganizował w Stanleyville wiec. Po wiecu wybuchły spontaniczne zamieszki, w rozbiciu których zginęło 30 osób. W listopadzie został zatrzymany za podżeganie do rozruchów. Skazano go na pół roku więzienia. Za kratami spędził trzy miesiące. Wypuszczono go w ramach przygotowań do belgijsko-kongijskiej konferencji okrągłego stołu.
Premier Konga W brukselskiej konferencji w styczniu 1960 opowiedział się za utworzeniem niepodległego i niesfederalizowanego Konga. W maju odbyły się w Kongu wybory parlamentarne zakończone sukcesem MNC, który to zdobył 25% głosów. Po wyborach Lumumba został premierem, z kolei Joseph Kasavubu prezydentem.