Paweł Malicki swoją drogę taneczną rozpoczął w Studio Tańca Współczesnego „Plus” w Koninie, gdzie uczył się technik od show i disco dance przez modern do akrobatyki. W latach 2004–2006 był tancerzem kaliskiego Teatru Tańca „Alter”. W roku 2006 ukończył Państwowe Pomaturalne Studium Kształcenia Animatorów Kultury w Kaliszu – specjalność: taniec współczesny. W tym samym roku otrzymał indywidualną nagrodę na Międzynarodowych Prezentacjach Tańca Współczesnego w Kaliszu.
W maju 2007 zwyciężył w polskiej edycji konkursu Solo & Duo Dance Festival, co zakwalifikowało go do edycji międzynarodowej w Budapeszcie. Tam otrzymał w 2008 roku nagrodę główną The Best Performance za choreografię 46. W 2009 roku uzyskał dyplom Ogólnokształcącej Szkoły Baletowej w Poznaniu. Od roku 2006 jest związany z Polskim Teatrem Tańca, tańczy prawie w całym repertuarze, podejmuje też aktywność choreograficzną w ramach Atelier Polskiego Teatru Tańca.