Aos 11 anos, Paulo Menezes começou a praticar o Jiu-Jitsu com o professor Amélio Arruda. Com 15, despertou sua paixão pelo Judô e se matriculou na Academia Marzullo. Foi atleta e mais adiante professor, lecionando por cinco anos.
Até vir a fundar a Academia, Paulo Menezes foi atleta da Universidade Gama Filho por 5 anos e atleta do Clube de Regatas do Flamengo por 2 anos, mesmo clube onde terminou sua carreira esportiva.
Ao longo de sua carreira esportiva, ele foi tetra-campeão estadual e vice-campeão brasileiro, tendo competido no exterior no Torneio de Colorado Springs (EUA) e Torneio Guido Siene (Itália).
Dando aulas na Academia Marzullo e em alguns colégios, sentiu a necessidade de ministrar aulas em uma academia própria. Escolheu o bairro do Ingá, mais precisamente na Rua Visconde de Moraes, nº 270 para ser o local de sua academia. A princípio alugou uma sala de 28m². Após 5 anos alugou a sala da frente que se tornou sala de ginástica e musculação.
Após 25 anos no Ingá, conseguiu uma sede própria com 3 andares num total de 520 metros². Situada agora na rua Visconde de Moraes, 256, ampliou suas atividades.
Como professor visitou e fez cursos na França, Japão e Suíça.
Paulo Menezes é formado em Educação Física, pós-graduado em Técnicas de Ensino e pós-graduado em Judô.
A Academia Paulo Menezes hoje tem 34 anos e já recebe os filhos dos ex-alunos que treinavam quando crianças.
.