dr n. med., w roku 2005 ukończył kierunek Biotechnologia Szkoły Głównej Gospodarstwa Wiejskiego. W toku studiów interesował się cytogenetyczną identyfikacją transgenicznych fragmentów DNA w roślinach modyfikowanych genetycznie. Ostatni rok studiów odbył w Hiroshima University w ramach stypendium przyznanego przez rząd Japonii. W latach 2005-2009 jako pracownik naukowy Kliniki Gastroenterologii i Hepatologii CMKP, rozwijał metody analizy w badaniach dotyczących identyfikacji genetycznych markerów ryzyka występowania chorób zapalnych przewodu pokarmowego. Badania z zakresu genetyki populacji dr Gaj kontynuował skupiając się na ogólnogenomowej analizie asocjacji markerów genetycznych (GWAS) w chorobach nowotworowych (rak jelita grubego, rak prostaty) oraz chorobach neurodegeneracyjnych takich jak choroba Alzheimera. Poza badaniami z zakresu genetyki populacji zainteresowania dr Pawła Gaja skupiają się również wokół wykorzystania technologii sekwencjonowania nowej generacji NGS do identyfikacji wariantów genetycznych odpowiedzialnych za rzadko występujące choroby dziedziczne. Dr Gaj jest autorem kilkunastu oryginalnych prac naukowych, z których w sześciu jest pierwszym autorem.
Od kwietnia 2013 dr Gaj pracuje Zakładzie Immunologii WUM, w grupie bioinformatycznej kierowanej przez dr Radosława Zagożdżona.