Mit ca. zehn oder elf Jahren lernte Paulo zum ersten Mal einen Capoeira-Meister kennen. Er hieß João de Barros und war Leiter einer folkloristischen Gruppe ("Grupo Folclórico João de Barros"), in der auch Paulos Onkel arbeitete. Sein Onkel war zudem in vielen anderen Gruppen tätig, wie zum Beispiel der des berühmten Mestre ("Meister") Dinho, Evandro und Badaró und reiste mit ihnen in mehrere brasilianische Städte und ins Ausland (Europa und die USA).
Von Zeit zu Zeit kamen vier Capoeiristas, Freunde seines Onkels, zu Besuch. Es waren Dimola (aber nicht der berühmte Dimola vom Mercado Modelo), Val, Maguila und Caboquinho, die heute alle nicht mehr in Brasilien leben. Manchmal hinterließen sie nur eine Nachricht, die Paulo seinem Onkel ausrichten sollte. Er sollte mitteilen, dass Val, Caboquinho und Maguila da gewesen wären und nun am Strand trainieren würden. Da sich das Haus von Paulos Großmutter direkt am Strand befand, beobachtete Paulo die drei immer vom Fenster aus, wie sie die unglaublichen Bewegungen der Capoeira und die perfekten Saltos machten. Und Paulo wollte so sein wie sie. Aber er hatte nicht die Möglichkeit, diese Kunst, die er sehr bewunderte, auszuüben. Capoeira war in dieser Zeit noch sehr verrufen und seine Großmutter hätte ihm niemals erlaubt, an solch einem Training teilzunehmen. Paulos Onkel nahm ihn immer wieder mit zu Auftritten und Proben, fragte ihn jedoch niemals, ob er Capoeira trainieren wolle.
Jedes Wochenende war Paulo glücklich, weil dies die Zeit war, um zum Strand zu gehen. Und natürlich versuchte er, ein paar der Bewegungen nachzuahmen, die er zuvor am Fenster beobachtet hatte. Aber alleine, ohne einen Capoeirista, der ihn unterrichtete, war es sehr schwer.

Die erste Begegnung mit einem Kampfsport
Die Zeit verging und Paulo zog zu seiner Patentante und deren Mann. Sein Patenonkel war der erste, der ihn mit dem Kampfsport Karate bekannt machte. Damals hatte dieser den dritten Dan und war Paulos erster Meister. Er unterrichtete in einem Fitnessstudio in Camaçarí.
Doch selbst in der Zeit in der Paulo Karate trainierte, vergaß er doch niemals Capoeira. Er widmete sich mit großem Eifer dem Karate-Training und schon als er den gelben Gürtel besaß, erlangte er in einem Wettkampf den dritten Platz.
Bei einem weiteren Wettkampf wurde ihm in Folge eines gewalttätigen Trittes ein Bein gebrochen und damit war für Paulo das Kapitel Karate beendet.

Der Wandel in Paulos Leben
Nach dem Tod seiner Großmutter zog er zu seiner Mutter, die in dieser Zeit noch sehr arm war. Er musste sogar Picolé (Eis am Stiel) verkaufen, um seinen Lebensunterhalt zu sichern.
Das Leben war nicht leicht für ihn. Kurze Zeit zuvor hatte es ihm noch an nichts gemangelt, und nun hatte er gar nichts mehr. Er lebte in einem sehr gefährlichen Viertel und lernte die dunklen Seiten des Lebens kennen. Aber auch in dieser schwierigen Situation ließ er seine schulische Laufbahn nicht schleifen. Er arbeitete tagsüber und besuchte eine Abendschule. Obwohl es in seiner Umgebung üblich war, ließ er sich niemals in Drogendelikte oder Überfälle verwickeln.

Auf dem Weg zu einem Capoeirista
In dieser Zeit lernte Paulo eine Frau kennen, die heute Mutter seiner Tochter ist. Ihr Schwager Neto lud Paulo eines Tages ein, zu seinem Capoeira-Training zu kommen. Da Paulo nicht über die finanziellen Mittel verfügte, ließ ihn der Capoeirameister Iran zunächst kostenlos trainieren.
Nun war er glücklich, weil dies seine erste Möglichkeit war, die Kunst zu trainieren, von der er immer geträumt hatte.
Am Tag seiner ersten Unterrichtsstunde ging er noch davon aus, dass Capoeira für ihn nicht allzu schwer sein würde, da ihm schon viele Bewegungen dieses Kampftanzes geläufig waren. Er hatte jedoch nicht bedacht, dass er immer nur Zuschauer gewesen war und es selbst noch nie praktiziert hatte. Nach seiner ersten Stunde hatte sich seine Meinung geändert und er verstand, dass Capoeira eine sehr komplexe Kunst ist.
Heute ist er Mestre Neto und Mestre Iran sehr dankbar, weil sie ihn auf den Weg der Capoeira gebracht haben.
Paulo trainierte fast zwei Jahre mit der Gruppe Aliba-Obá von Mestre Neto. Danach wurde er von verschiedenen Lehrern und Meistern unterrichtet, bis er schließlich zu Prof. Edmundo und der Gruppe System kam. Diese Gruppe gehört zu Brilha Bahia von Mestre Zeú, der der Meister von vielen Capoeiristas ist.
Später entstand die Gruppe Nação Capoeira, der sich Mestre Zeú und alle seine Schüler anschlossen.