Antes de iniciar sua carreira no futebol de campo, jogava futebol de salão pela equipe AABB, um clube de Campinas, sua cidade natal. Após bom tempo dedicando-se ao futsal, em 1998, com 15 anos de idade, iniciou sua carreira como infantil no São Paulo, clube onde conquistou seus primeiros títulos, e permaneceu até o ano de 2001. Em dezembro de 2001 com 18 anos, transferiu-se para o CSA, de Alagoas, porém permaneceu apenas três meses no clube.
Em março de 2002, Paulo André voltou para seu estado de origem, São Paulo, onde atuou pelas categorias de base do Águas de Lindoia. Conquistou o título da Séria A-2 Paulista de juniores. Naquele ano, teve suas primeiras oportunidades como profissional, onde ajudou o clube a subir da quinta para a quarta divisão estadual, porém voltou ao time de juniores. Ainda em 2002, teve uma rápida passagem nas divisões de base do Vasco da Gama[1].
Guarani
Em janeiro de 2003, transferiu-se ao Guarani, clube de sua cidade, Campinas, ficou por um ano entre os juniores, e em fevereiro de 2004 fez sua estreia entre os profissionais. Permaneceu no clube no período de janeiro de 2003 a junho de 2005, atuando 55 vezes e marcando 6 gols.
Atlético Paranaense
Em junho de 2005, foi contratado pelo Atlético Paranaense, formando dupla com Danilo Larangeira e tornando-se titular, capitão e vice-artilheiro do time na temporada, além de ter sido eleito como um dos cinco melhores zagueiros do país, pelo Bola de Prata 2005 da Revista Placar. Em 2006, como capitão da equipe, recebeu o título de melhor zagueiro do estado do Paraná, pela Federação Paranaense de Futebol. Permaneceu no clube de junho de 2005 a junho de 2006, atuou 54 vezes, marcando 8 gols.
Le Mans
Após negociações do Atlético com o presidente do Le Mans, Henri Legarda, o zagueiro foi vendido ao time francês, em junho de 2006.[2][3] O contrato firmado foi de quatro anos e meio.[4] Marcou seu primeiro gol pelo clube no dia 16 de setembro de 2006. Em poucos jogos, conquistou a posição de titular, porém sofreu uma grave lesão no tendão e ficou por muito tempo fora. Atuou 43 vezes, marcando 5 gols.
Corinthians
No dia 31 de julho de 2009, foi apresentado como nova contratação do Corinthians, com contrato de empréstimo até agosto de 2010.[5][6] Mesmo não sendo considerado titular, devido as lesões de William e Chicão, passou a jogar muitas partidas, mais até do que os titulares.
Com a aposentadoria de William, se tornou titular provisório do Corinthians, mas uma lesão no joelho esquerdo o tirou dos gramados por seis meses. Em abril de 2011, o zagueiro retornou ao time como reserva e em outubro conseguiu a titularidade após o afastamento de Chicão. O zagueiro foi peça importante na conquista do Campeonato Brasileiro e terminou o ano recebendo o troféu Bola de Prata 2011 da Revista Placar.
Shanghai Shenhua
No dia 12 de fevereiro de 2014, o jogador de 30 anos tomou a decisão de deixar o clube para transferir-se ao Shanghai Shenhua, da China, após uma conversa com o diretor de futebol do Corinthians, Ronaldo Ximenes.[7]
Cruzeiro
Já no dia 10 de fevereiro de 2015, foi apresentado como reforço do Cruzeiro.[8]
Retorno ao Athletico Paranaense e aposentadoria
Em dezembro de 2015, retornou ao rubro negro paranaense, conquistando seus últimos títulos como jogador. Em junho de 2019, o jogador anunciou a sua aposentadoria, assumindo o cargo de diretor de futebol do clube.[9]
Outras atividades
Paulo André é um apreciador de literatura, xadrez e pintura. No dia 15 de fevereiro de 2011 criou o Instituto Paulo André, uma organização sem fins lucrativos criada com o objetivo de oferecer projetos socioeducativos nas áreas de esporte e cultura para que crianças e jovens, com sede em sua cidade natal, Campinas. Em março de 2012, lançou o livro O Jogo da Minha Vida - Histórias e reflexões de um atleta, com reflexões críticas sobre o mundo do futebol.[10]
Já no ano de 2013, em fevereiro promoveu um leilão com o intuito de arrecadar dinheiro para instituições de caridade.[11] Em novembro foi um líderes do movimento Bom Senso Futebol Clube.[12]
Em setembro 2018, manifestou-se contra Jair Bolsonaro ao assinar o Manifesto Democracia Sim, feito por artistas e intelectuais. Ele foi o único jogador de futebol em atividade a participar do movimento. Em outubro, antes de partida contra o Bahia, recusou-se a exibir a camiseta em apoio a Bolsonaro.[13][14]
Jogos pelo Corinthians
Expanda a caixa de informações para conferir todos os jogos deste jogador, pelo Corinthians.