Jeho hokejové začiatky siahajú do rodného mesta do klubu Spartak ZŤS Dubnica nad Váhom.
S hokejom sa dokonale skamarátil, keď mal šesť rokov. S vrcholovým hokejom začal v sezóne 1992/1993 za Duklu Trenčín. Počas nasledujúcej sezóny debutoval v NHL ako hráč Ottawy Senators. Počas troch rokov účinkovania v Ottawe hrával väčšinou v mužstve Prince Edward Island Senators.
V klube St. Louis Blues vytvoril spolu s Michalom Handzušom a Ľubošom Bartečkom produktívny útok nazývaný Slovak line. V roku 2000 bolo ocenený individuálnou trofejou Lady Byng Memorial Trophy pre najslušnejšieho hráča. K trofeji prispel aj okamih, kedy mohol vystreliť, dať gól a zabezpečiť si tým prémiu 500 000 USD, ale on prihral Scottovi Youngovi, ktorému by gól priniesol 300 000 USD. Ten bol však natoľko prekvapený, že gól napokon nedal. Na otázky novinárov prečo nestrelil ale nahral, Paľo odpovedal, že Scott potreboval gól. Lady Byng Memorial Trophy je pre hokejistov prestížna cena za technickú a umeleckú dokonalosť, ako aj za džentlmenstvo na ľade.
V sezóne 2004/2005, počas prerušenia hokejovej súťaže – lockoutu v NHL, bol hráčom za Duklu Trenčín. Väčšinu sezóny v jednom útoku s Mariánom Hossom a Mariánom Gáboríkom. Tu sa stal najproduktívnejším hráčom súťaže, dosiahol rekordných 82 bodov v základnej časti.
Pôsobil aj v klube Los Angeles Kings a Minnesota Wild, kde vytvoril produktívnu dvojicu s Mariánom Gáboríkom. V tomto klube pôsobil aj ďalší Slovák Branko Radivojevič. 10.7.2008 podpísal zmluvu s tímom Vancouver Canucks.
Pred sezónou 2010/2011 sa stal hráčom ruského klubu KHL Lokomotiv Jaroslavľ, kde v play-off bodoval desať zápasov po sebe.
V roku 2003 sa stal najlepším hokejistom Slovenska v ankete Zlatý puk.
V rokoch 1996, 2003 /bronz, Fínsko/, 2004, 2005, 2007 a 2011 reprezentoval Slovensko na majstrovstvách sveta, v rokoch 2002, 2006 a 2010 na ZOH a v rokoch 1996 a 2004 na Svetovom pohári.
V roku 2002 sa oženil a s manželkou Máriou majú dve deti: syna Lucasa a dcéru Zaru. Syn Tobias /dvojča Zary/ umrel štyri dni po narodení pre vážnu chybu dýchacích ciest.
Bol hráčom s vysokou kreativitou, bol hokejovým umelcom a zároveň charizmatickým človekom. Hokej hral majstrovsky a bravúrne zvládal svoje líderstvo.
V roku 2011 sa po bohatej reprezentačnej kariére emotívne rozlúčil počas majstrovstiev sveta, kedy dostal aj titul Najlepší útočník SR 2011.
7. septembra 2011 tragicky zahynul pri havárií lietadla Jak-42, kde zahynul aj celý hokejový tím Lokomotiv Jaroslavľ. Pri štarte lietadla došlo k chybe posádky, následne lietadlo narazilo do stožiaru antény a krátko na to havarovalo. Časť lietadla spadla do rieky Volga.
6. júna 2012 bol zaradený do siene slávy Slovenského zväzu ľadového hokeja.
