Começou no Internacional (RS), estreando no profissional em 1960, contra o Peñarol, no Uruguai.
Em 1961, foi emprestado ao São Paulo (RS), porém não se adaptou à cidade e retornou a Porto Alegre. Foi sondado pelo Bologna da Itália, mas o Internacional pediu um valor muito alto e a negociação não saiu.
Emprestado ao Londrina em 1962, enfrentou o Coritiba na fase decisiva do Paranaense e, com dois gols dele, o Londrina tornou-se campeão paranaense. Permaneceu no norte do estado até 1963.
De 1964 a 1967, defendeu o Ferroviário de Curitiba. Fez muitos gols na dupla Atletiba e foi bicampeão paranaense em 1965-1966.
No final de 1967, defendeu o Coritiba por empréstimo na partida contra a temida seleção da Hungria. O alviverde venceu por 1x0 com gol de Oromar e passe de Paulo Vecchio.
Em 1968, Paulo foi emprestado ao Metropol de Criciúma.
Em abril do mesmo ano, o Atlético (PR) tentou trazê-lo por empréstimo para as disputas do Campeonato Paranaense. Paulo ficou treinando durante uma semana, mas sem acertar um contrato. Quando o Atlético (PR) finalmente ofereceu-lhe um contrato para assinatura, Paulo recebeu uma ligação da secretária de Munir Kaluf, que se identificou ao telefone como esposa do atleta. Ela pediu para Paulo Vecchio apresentar-se na sede do Coritiba, pois este pretendia adquirir seu passe.
Paulo Vecchio preferiu jogar no Coritiba e se deu bem: Até 1973, ano em que encerrou a carreira, foi quatro vezes campeão paranaense pelo alviverde.