Paulo Oliveira nasceu em Vila do Conde, em 1979. Iniciou os estudos musicais aos nove anos com Joaquim Bento. Seguidamente ingressou na Academia de Música de S. Pio X como bolseiro da Fundação Dr. Elias de Aguiar. Nesta instituição estudou com Margarida Almeida e Felipe Silvestre, tendo finalizado o Curso Complementar de Piano em 1998 com a classificação máxima.
Posteriormente estudou com Tania Achot, concluindo o Curso Superior de Piano na Escola Superior de Música de Lisboa, uma vez mais com as mais altas classificações.
Continuou a sua formação com Sequeira Costa na Universidade do Kansas, com quem estudou durante quase uma década, herdando assim os mais fiéis conhecimentos da era dourada do piano, que o seu mestre tinha recebido diretamente de Vianna da Motta, Mark Hamburg, Edwin Fischer, Marguerite Long e Jacques Février. Nesta Universidade concluiu estudos de mestrado em 2005, como bolseiro da Fundação Calouste Gulbenkian. Posteriormente, em 2009, concluiu com distinção o seu doutoramento com uma bolsa de estudos da Fundação para a Ciência e Tecnologia.
Outros professores relevantes na sua formação foram Helena Sá e Costa, Luiz de Moura Castro, Andrei Diev, Vladimir Viardo, Vitaly Margulis, Aldo Ciccolini, Paul Badura-Skoda e Dmitri Bashkirov.
Foi distinguido com diversos prémios em concursos nacionais e internacionais, destacando-se o prémio que obteve no Concurso Internacional de Piano Vianna da Motta” o 1.º prémio no Concurso Internacional Bartók-Kabalevsky-Prokofiev, o 2.º prémio no Concurso de Interpretação do Estoril | Prémio El Corte Inglés e o 1.º prémio no Festival Jovens Pianistas 2010 – Prémio Chopin, organizado pela Orquestra Metropolitana de Lisboa. Foi ainda vencedor da Kansas University Symphony Orchestra Concerto Competition. O duo que mantém com a violoncelista Teresa Valente Pereira foi premiado num recital realizado no Palau de la Música Catalan” em Barcelona.
Paulo Oliveira tem-se apresentado a solo, com orquestra e em música de câmara em Portugal, Espanha, Andorra, Itália, França, Reino Unido, Polónia, Brasil, Estados Unidos da América, e gravou para a RDP – Antena 2, Radio France e Catalunya Ràdio.
Tocou a solo com a Orquestra Sinfónica da Universidade do Kansas, Orquestra Clássica de Espinho, Orquestra do Algarve, Orquestra do Norte, Orquestra Metropolitana de Lisboa e Orquestra Sinfónica Portuguesa, sob a direção dos maestros Nicholas Uljanov, Steven McDonald, Pedro Neves, Ferreira Lobo, Cesário Costa e Daniel Klajner.
Paulo Oliveira concilia a sua atividade concertística com o ensino. Foi professor de piano no Conservatório Nacional em Lisboa, na Escola Profissional Metropolitana e é atualmente docente no Instituto Piaget, na Escola de Música de Nossa Senhora do Cabo e no Conservatório de Música da Metropolitana. Tem sido regularmente convidado a orientar masterclasses e integrou por diversas vezes júris de concursos de piano.
É membro fundador da delegação portuguesa da European Piano Teachers Association.