He began playing football at Rosenhøj BK in Denmark, after that he played for Danish clubs Hvidovre IF and Brøndby IF. The midfielder made his debut for Ajax on 17 September 2006 in the league match Roda JC – Ajax (2–0). Krohn-Dehli played for a number of Danish clubs before joining Ajax from Brøndby IF. Krohn-Dehli excelled as a youth team player for Ajax under Danny Blind. In 2004 however, he was allowed to leave Ajax by manager Ronald Koeman and he joined RKC Waalwijk on a free transfer. There he made his professional debut on 15 August 2004 in a goalless draw against FC Groningen. Two years later, he was re-signed by Ajax on a free transfer until 2009. He made his debut for the Denmark national football team in an Euro 2008 qualification match against Liechtenstein on 11 October 2006. After the winter break with only three appearances for Ajax he was sent on loan to Sparta Rotterdam on 31 January 2007 for the remainder of the season. Five days later he made his first out of 12 appearances for Sparta against Roda JC. After his spell at Sparta and the summer break he returned to Ajax for the 2007–08 season.
Ajax announced on 29 August 2008 that they would transfer Krohn-Dehli to Danish Brøndby IF. He made his debut two days later on 31 August against FC Copenhagen.
On 21 August it was announced, Krohn-Dehli would be joining RC Celta after completing a medical.
Krohn-Dehli scoring the winner against the Netherlands at Euro 2012
Krohn-Dehli scored the only goal in Denmark's 1–0 victory over the Netherlands in UEFA Euro 2012. After that match, Krohn-Dehli said he was satisfied with scoring and told reporters after the game, "It's a little bit special for me as I played for eight years in Holland and have a Dutch girlfriend, so I think the whole family was cheering in Holland. I found space to move in, and I'm very happy I was able to score one against the Dutch. It's now not so necessary to win the rest [of the group games] in order to advance to the knockout stage.". He also scored the lone goal for Denmark in the final group stage game against Germany, a 1–2 loss.