Nasceu em 1948, na cidade de São Paulo. De origem humilde, entrou em contato com a literatura na adolescência, graças a uma biblioteca que sua família recebeu em doação. Aos dezenove anos começou a trabalhar na Telesp (Companhia Telefônica de São Paulo), onde participou dos concursos literários internos promovidos pela revista "Entrelinhas". Por duas vezes foi o primeiro colocado. Cursou e abandonou as faculdades de Desenho Industrial e Sociologia.
Sob o título de "A Cabra", publicou em janeiro de 1989, no suplemento literário da Folha de S. Paulo, o embrião do que viria a ser seu romance de estreia, aos 53 anos, "À Margem da Linha" (2001), lançado em 2001.
No mesmo ano, Rodrigues conquistou o prêmio APCA (Associação paulista dos críticos de arte) como escritor revelação. À margem da linha ganhou, ainda, edições em Portugal, pela editora Temas e debates (2005), e na Espanha, pela catalã Edicions del salobre (2006).
Em 2004, lançou o livro de contos "Redemoninhos", também pela Cosac Naify.
Atualmente, Paulo Rodrigues é assessor sindical na área de telecomunicações.