Karadeniz played his first professional match for Trabzonspor in the 1999–00 season at the senior level and made ten appearances. He was at first used in defensive roles by his manager, but was gradually given a more and more offensive role in the team until the 2003–04 season when he was given a much freer rein in midfield. His lightning step and effective understanding with teammate Fatih Tekke enabled him to lead the club in scoring that season with 13 goals.
On 13 March 2008, he signed a 5-year deal with the Russian club Rubin Kazan worth €8.7 million. Karadeniz mentioned that it was sad for him to leave Turkey and also said he chose the club because he felt that if he had joined a big team in Europe his club would not have gotten as much money for him. Karadeniz also said that another factor that persuaded him is that the region the club is from has a large Muslim population (Tatarstan) and Karadeniz feels comfortable living amongst people of the same religion as him. With the team he won the Russian Premier League 2008.
On 20 October 2009, Karadeniz scored the winning goal to shock the Barcelona fans at Camp Nou, winning the match for Rubin Kazan.