Born in Sorel-Tracy, Quebec, Fleury played for the Quebec Major Junior Hockey League (QMJHL) for the Cape Breton Screaming Eagles during the 2000-2001 season. He won a silver medal with Team Canada in the World Junior Championships. He was drafted first overall in the 2003 NHL Entry Draft.
Fleury made his debut in the 2003-2004 season at 18 years old, making him the youngest goalie in the league. He recorded an impressive 46-save performance in his first start, and recorded his first win the next game.
NHL play was on hold for the 2004-2005 season due to a labor dispute. Fleury played for the Penguins AHL affiliate, the Wilkes-Barre/Scranton Penguins, putting up a 29-16-4 record and a .901 save percentage. He returned to the Penguins organization on October 10, 2005.
Fleury has been somewhat injury prone, suffering a high ankle sprain in December 2007. He did not return until early March. Midway through the 2008-2009 season, he suffered another "lower body injury" and was benched for nearly a month. He still remains the starting goaltender, despite poor numbers for the season.