Born in Žilina. Bajza began his career with Považská Bystrica, later Pavol joined Dubnica in 2006, aged just 15. After progressing through the Dubnica youth system, Bajza (18 years, 175 days) made his first team debut for MFK Dubnica on 27 February 2010 against MŠK Žilina.
On 22 March 2012, Dubnica agreed a fee with Serie A club Parma for Bajza. He had signed a three-year contract with the club, with effect from 1 July 2012. He made his debut for Parma on 19 May 2013 against US Palermo. He replaced Antonio Mirante after 42 minutes.