Zaznaczył się jako jeden z prężniejszych animatorów sceny koncertowej Programu 3.
W międzyczasie pracy w „Trójce”, Paweł Kostrzewa był głównym zarządzającym muzyką w Programie Pierwszym PR. Do „Jedynki” przeszedł 1 lipca 2005, rozstając się tym samym z Programem 3. Został jednym z prowadzących przedpołudniową audycję muzyczną Cztery pory roku i Lato z Radiem 2007. Z Polskiego Radia odszedł pod koniec listopada 2007, po 18 latach pracy. Od 2 czerwca 2008 do 1 grudnia 2008 pełnił stanowisko dyrektora programowego radia Eska Rock. Był odpowiedzialny za realizację strategii programowej stacji po rozszerzeniu jej zasięgu nadawania na 18 rynków. Prowadził tam autorską audycję pROCKreacja.
Współpracował również z radiem BBC. Ma na koncie ponad 10 tys. godzin spędzonych przed mikrofonem radiowym.
Od 21 marca 2026 roku powrócił na antenę Trójki z audycją Trójkowy ekspres.
Pozostała działalność Jest autorem licznych recenzji i artykułów na temat rocka publikowanych w „Tylko Rocku”, „Teraz Rocku”, „Muzie”, „XL”, „Gazecie Wyborczej”, „Dzienniku” i serwisie internetowym Onet.pl.