O Major Piloto-Aviador Paulo Rebelo nasceu a 4 de abril de 1986, na Freguesia de Moreira de Cónegos, Guimarães.
É licenciado (pré-Bolonha) em Ciências Militares Aeronáuticas pela Academia da Força Aérea (2004-2008).
Efetuou o seu tirocínio na Base Aérea de Laughlin, Texas, Estados Unidos da América, onde voou as aeronaves T-6 Texan II e T-38C Talon, sendo brevetado em 2010.
Após frequência do Curso Complementar de Pilotagem em Aviões de Combate, na Base Aérea N.º 11, em Beja, foi colocado na Esquadra 201 “Falcões” em setembro de 2011, onde completou a qualificação de piloto operacional em F-16M.
Desde então, obteve a qualificação de comandante de parelha e de esquadrilha em voo, e exerceu funções de Oficial de Uniformização e Avaliação, Chefe da Secção de Mobilidade, Chefe da Secção de Planeamento Operacional, Oficial de Guerra Eletrónica e Chefe da Secção de Tiro e Táticas.
Como Piloto operacional esteve presente em diversas missões e exercícios nacionais e internacionais, entre os quais se destacam Baltic Air Policing e Nato Assurance Measures. No ano de 2018 foi indigitado, em acumulação, para a posição de Targeteer da Força de Reação Imediata, CCOM.
Em 2021, concluiu o Curso de Promoção a Oficial Superior no Instituto Universitário Militar, regressando para a Base Aérea de Monte Real até setembro do mesmo ano quando foi indigitado como Oficial para o intercâmbio, treino e formação junto da Força Aérea Belga, tendo sido colocado na Base Aérea de Florennes, Reino da Bélgica.
Em 2022, devido à invasão da Ucrânia, participou ao serviço da Força Aérea Belga na missão enhanced Vigilance Activities, tendo estado destacado na Base Aérea de Amari, Estónia.
Regressou à Base Aérea nº5 em setembro de 2023 para assumir o cargo de Oficial de Operação da Esquadra 201.
Atualmente, conta com cerca de 1800 horas de voo em F-16AM.
É casado e tem dois filhos.