Cria da escola de samba Filhos do Tororó, Vicente de Paulo é autor, ao lado de Russo, do samba-enredo “Carnaval, fantástico show da vida”, com o qual a escola desfilou no Carnaval de 1974. Sua trajetória como compositor de sambas-enredo, porém, já havia começado um ano antes: na ocasião em que foi eleito Cidadão Samba da escola, o sambista concorreu, ao lado de Russo e Nelson Cara, na disputa para o enredo “50 anos de Yalorixá de Mãe Menininha do Gantois”, sem sucesso.

Nos anos posteriores, Vicente de Paulo voltaria a compor outros bons sambas-enredo. Primeiramente, por sua escola do coração, quando concorreu – e perdeu – nas disputas de 1975 (“Memórias de Mestre Bimba”, com Paulo Ney Berenguer) e de 1976 (“Homenagem a Nosso Senhor do Bonfim”). Depois, nos Diplomatas de Amaralina, ao lado do eterno parceiro Russo e de Jonas Madureira, logrou êxito no concurso interno, levando à Avenida o samba-enredo “Histórias dos Carnavais passados”, com o qual a escola sagrou-se tricampeã.