In 1992 Paweł Brożek began his career at Polonia Białogon Kielce, together with his twin brother Piotr. In 1998 he moved to Zabrze to play for SMS Zabrze team. A half a year later he joined Wisła Kraków, together with his brother.
He made his debut for Wisła Kraków in Ekstraklasa on 8 April 2001 in a match against Górnik Zabrze. On 21 April 2001 he scored his first goal in the Ekstraklasa in a match against Odra Wodzisław. On May 2001 Brożek signed a new 10-year contract with Wisła Kraków. He won the Ekstraklasa championship in 2000–01 season with Wisła Kraków. In 2002 he was loaned to ŁKS Łódź to play in the Polish First League. A half year later he returned to Wisła Kraków and won with his second club Ekstraklasa title, in 2002–03 season. In 2004 he was loaned to GKS Katowice for a year and a half. He was a stand out player at GKS Katowice. On December 2004 he was invited for a trial together with his twin brother Piotr by West Ham United.
On January 2005 Paweł Brożek returned to Wisła Kraków, because the then Wisła manager Werner Lička wanted him to come back from loan. Brożek won the Ekstraklasa title in 2004–05 season with Wisła Kraków. In 2005–06 season he began to play regularly for his side, Wisła Kraków first squad. Subsequently he scored 13 goals in 30 matches. In 2006–07 season Brożek played very well in UEFA Cup, where he scored 4 goals in group stage matches against AS Nancy, FC Basel and Feyenoord Rotterdam. In 2007–08 season Brożek scored 23 goals in 27 matches and led Wisła Kraków to achieve the Ekstraklasa title. He was the Ekstraklasa Top Goalscorer in 2007–08 season. In 2008–09 season he won his sixth Ekstraklasa title with Wisła and was the Ekstraklasa Top Goalscorer for the second time in a row. In the following 2009–10 season, Brożek led his team in goals and assists while Wisła finished second in the league.
In January 2011, Paweł together with his twin brother Piotr, joined Turkish Süper Lig side Trabzonspor on a two-and-a-half year deal for an undisclosed fee from Wisła Kraków. Brożek made his debut for Trabzonspor in a Turkish Cup match against Beşiktaş on 26 January 2011, assisting Alanzinho's goal with a back-heel pass. In the 2010–11 Süper Lig season, he contributed with two goals and two assists for the eventual runners-up. In the following campaign, Brożek could not establish himself in the Trabzonspor starting line-up, blocked by Turkish international Burak Yılmaz, who played as the sole striker in the system preferred by coach Şenol Güneş.
On 29 January 2012, Brożek agreed terms to join Scottish Premier League outfit Celtic on loan from Trabzonspor until the end of the season, subject to a medical. The following day, he signed a contract with Celtic after passing the medical exams. He was given the number 17 shirt. On 8 February 2012, he made his debut in the 4:0 win over Heart of Midlothian in a Scottish Premier League match after coming on as a second half substitute for Scott Brown. He made three appearances for the eventual league champions during the 2011–12 season.