Paul Wheeler przygodę z perkusją rozpoczął w wieku szesnastu lat, grając w lokalnych zespołach w Sydney. Już po trzech latach dostrzeżony został przez Iva Davies’a, oferującego mu współpracę w grupie Icehouse. Ten właśnie moment dał początek jego profesjonalnej karierze muzyka, a także rozwijanie się u boku zespołu przez kolejne lata po dzień dzisiejszy.
Jego wspólpraca z Icehouse przyniosła wydanie „Measure for Measure” oraz „Man of Colours”, której producentem był David Lord. Był to jeden z najlepiej sprzedających się albumów w Australii, a dwa single znajdujące się na nim podbiły listy amerykańskiego Billboardu. Kolejny krążek – „Code Blue” (producent – Nick Launay), a także „Big Wheel” (David Lord) ujawniły kolejne utwory, które zawładnęły sercami fanów na całym świecie. Wraz z zespołem koncertował po Europie, Ameryce, Australii i Nowej Zelandii. Uczestniczyli wspólnie w „The Cars”, Madison Squares Gardens w Nowym Jorku, Montreaux Pop Festival w Szwajcarii oraz w „The Johnny Carson Show”, „NBC Today”, czy „Top of The Pops UK”. W czasie wieloletniej współpracy z Icehouse miał okazję pracować z wieloma artystami na całym świecie. Na długiej liście muzyków znaleźć można Anthony’ego Callea, Vincenta Stone’a, Richarda Claptona, Briana Nadda, Nikka Costa, Iana Mossa, Choirboys, Russella Morrisa, Darryla Ottona, Maxa Sharama i Marcia Hines. Na przełomie 2006 i 2007 roku występował z Choirboys, Noiseworks i Ianem Mossem w wielu stolicach i na światowych scenach. Swoich sił Paul spróbował również ze stylem country, grając z Jamesem Blundellem, Dianna Corcoran i Adamem Branem. Współpracę nawiązywał również z zespołami – The Whitlams, Hall & Oates, czy Sneaky Sound System. Z tym ostatnim pojawił się w „The Panel Christmas Wrap”, Rove Live i Sunrise, a także poświęcał się nagraniom do ich albumów. W roku 2003 pojawił się na krążkach Lo-Tel, których producentem był Rick Will. Tego samego roku pracował z Duncanem Jamesem. Wraz z nimi oraz z Johnem Maherem i Blondie koncertował po całym świecie.
Dziś Paul kontynuuję współpracę z Iva Daviesem i Icehouse, którzy w roku 2006 wzbili się do poziomu APRA oraz ARIA Hall of Fame. Zespół zapraszany jest na wiele wydarzeń i wystąpień na całej kuli ziemskiej.