Jego rodzina ze strony ojca pochodziła z Polski. Z powodu afrykańskich korzeni matki nazywał siebie "mieszańcem z Kurytyby". Jako dziewiętnastolatek wziął udział w Narodowym Tygodniu Poezji Awangardowej w Belo Horizonte, gdzie z racji młodego wieku i talentu zyskał przezwisko "Rimbaud z Kurytyby". Zresztą liczba barwnych przydomków, które do niego przylgnęły, była dość długa. Nazywano go również "kosmicznym polilingwistycznym parafianinem" (był poliglotą), "cwaniakowatym samurajem" (miał czarny pas w judo), "polskim caboclem z Parany" (caboclo w języku tupi oznacza tego, który przyszedł z lasu lub syna białego mężczyzny), "bandytą mówiącym po łacinie" lub "pokopanym Polakiem".
W Belo Horizonte Leminski nawiązał kontakt z czołowymi brazylijskimi przedstawicielami poezji konkretnej, między innymi z Haroldem de Campos, Déciem Pignatari i Augustem de Campos. To właśnie ci trzej poeci na początku lat pięćdziesiątych stworzyli grupę Noigandres, która zainicjowała ruch poezji konkretnej w Brazylii (manifest grupy został opublikowany w 1954 roku pod tytułem "Plan pilotażowy dla Poezji Konkretnej"). Rok później Leminski zadebiutował w czasopiśmie "Invenção" pięcioma poematami niepodporządkowanymi żadnym związkom semantycznym i syntaktycznym.
Poeta, pisarz, tłumacz, kompozytor…
Pracował jako nauczyciel historii na kursach przygotowawczych dla uczniów szkół średnich, a także jako dyrektor kreatywny oraz autor tekstów w agencji reklamowej. Jednocześnie publikował wiersze w wielu lokalnych czasopismach i liczne tomiki poetyckie, od niedawna dostępne w przekładzie na polski, parał się również krytyką literacką - recenzował głównie dzieła współczesnych autorów brazylijskich dla znanych czasopism i gazet o zasięgu krajowym: "Veja" i "Folha de São Paulo". Oprócz poezji pisał również eksperymentalne teksty prozą, m.in. "Catatau" i "Agora é que são elas") i biografie (Jezusa Chrystusa, Lwa Trockiego, brazylijskiego poety Cruz e Souza oraz japońskiego poety Bashō). Niektóre źródła podają, że znał sześć języków obcych, inne, że znał ich dziesięć. Przetłumaczył na język portugalski książki Yukio Mishimy, Alfred Jarry’ego, James Joyce’a, Petroniusza, Samuela Becketta, Johna Lennona, a także pojedyncze wiersze Majakowskiego i Mickiewicza. Był także kompozytorem i autorem tekstów dla wielu znanych piosenkarzy i muzyków (jego teksty śpiewały gwiazdy popularnej muzyki brazylijskiej: Caetano Veloso, Itamar Assumpção, Ney Matogrosso, Arnaldo Antunes). Miał trójkę dzieci i dwie żony, w tym poetkę Alice Ruiz.
Swą przygodę z poezją Paulo Leminski zaczął jako poeta konkretysta, następnie zbliżył się pod względem ideowym do grupy "poetów marginesu" (pisane przez nich wiersze odbijano na powielaczach i rozdawano na ulicach). Przeszedł również fascynację tropikalizmem, twórczością beatników oraz japońskim haiku, którego wpływ jest mocno widoczny w jego twórczości. W ostatnich czasach utracił stygmat "poety wyklętego" i wszedł na stałe do kanonu literatury brazylijskiej, będąc przedmiotem masowego uwielbienia i popkulturowej mody.
Polskie motywy twórczości
W swojej twórczości Lemiński wielokrotnie nawiązywał do polskich motywów. Bohaterem jego najsłynniejszego eksperymentu prozatorskiego "Catatau" (1975), wymykającego się klasyfikacjom pod względem gatunkowym, jest Krzysztof Arciszewski, generał artylerii, który zaciągnął się do służby w holenderskiej Kampanii Zachodnioindyjskiej. Dotarł on do Brazylii razem z ekspedycją wysłaną przeciw Hiszpanii i Portugalii. Ta historyczna postać posłużyła Leminskiemu jako inspiracja do stworzenia przewrotnej powiastki satyryczno-filozoficznej, której główny bohater, Kartezjusz (ale nie Descartes, tylko niejaki Renatus Cartesius), próbuje zrozumieć Brazylię. Pod wpływem tropikalnego klimatu i wypalenia niezidentyfikowanego zioła Kartezjusz oddaje się delirycznym rozmyślaniom w oczekiwaniu na Arciszewskiego, który pojawia się pod sam koniec tego literackiego eksperymentu, zupełnie pijany.