Pavla Gajdošíková vyrůstala v Otrokovicích a Bělově. Studovala herectví na Janáčkově konzervatoři v Ostravě pod vedením režiséra Václava Klemense. Ještě během studií nastoupila do Divadla Petra Bezruče, jehož členkou byla celých deset sezón. Ztvárnila zde řadu zásadních rolí např. Julii v Romeu a Julii, Soňu ve Strýčku Váňovi, Karolínu v Kazimírovi a Karolíně, Lucii ve Zbabělcích, Alžbětu v Richardu III., Sheeni v Mládí v hajzlu nebo Markétku v Mistrovi a Markétce. Její nejvýraznější rolí se stala Maryša, za kterou získala Cenu divadelní kritiky a Moravskoslezskou kulturní Cenu Jantar a byla také nominována na Cenu Thálie. Hostovala v Městském divadle Zlín, v Národním divadle Moravskoslezském, v Absintovém klubu Les Ostrava i na Letních shakespearovských slavnostech, kde se představila jako Ofélie v Hamletovi.
Od srpna 2020 je členkou souboru Divadla pod Palmovkou. V posledních sezónách zde ztvárnila například Dorou Idesovou v Žítkovských bohyních, Hermii v Snu noci svatojánské, Mařenku v Prodané nevěstě, Jill v inscenaci Vaříme s Elvisem, Marie Svobodovou v Encyklopedii akčního filmu či postavy v autorské inscenaci Bezruký Frantík.
Na filmovém plátně zazářila v hlavní roli dramatu Chyby (2021) režiséra Jana Prušinovského. Za postavu Emy získala Českého lva i Cenu české filmové kritiky. Objevila se také ve filmech Hrana zlomu, DonT Stop nebo v minisérii Hořící keř, a v řadě televizních seriálů např. Případy 1. oddělení, Zkáza Dejvického divadla, Místo zločinu Ostrava či Sedm schodů k moci.
Vedle herectví se dlouhodobě věnuje hudbě. Od dětství hraje na cimbál a kytaru. Dnes skládá vlastní písně a zpívá v kapele Tamala.
Hraje v inscenacích: