With the introduction of a semi-final at the 2004 contest, and due to Denmark's absence from the 2003 contest, Denmark's 2004 representative, Thomas Thordarsson, had to take part in the semi-final. His song, "Shame on You" did not reach the final, finishing 13th in a field of 22 contestants.
In 2005, DR made a bold step for Dansk Melodi Grand Prix. Artists were allowed, for the first time ever, to sing in a language other than Danish. Many of the entries that year were sung in English; however, against the odds, the winning song was sung in Danish. Jakob Sveistrup won Dansk Melodi Grand Prix with his song "Tænder på dig". It was later re-written for the Eurovision Song Contest 2005 to English as "Talking to You". Unlike the year before, Denmark secured a place in the final, finishing third in the semifinal. In the final he came 9th, guaranteeing Denmark a place in the final of the 2006 contest. A year later, Sidsel Ben Semmane sang "Twist of Love" in the final, but managed to finish 18th of 24 songs.
In 2007, after many poor results, Dansk Melodi Grand Prix adopted a semi-final format that had served well for the Swedish preselection, Melodifestivalen. Two semi-finals with 8 songs each were introduced, with the top 4 songs qualifying for the final. The 4 losing songs of each semi-final then took part in one of two wildcard rounds where the listeners of Danish radio stations P3 and P4 chose another two finalists. The winner under this new format, DQ with the song "Drama Queen" (a wildcard entrant), finished 18th in the semifinal, relegating Denmark again.
For the 2009 of Dansk Melodi Grand Prix, DR reverted to their one-night final, that was held on 31 January 2009. The final of 10 songs consisted of 6 songs from an open call of songs from the public, with 4 songs being invited by DR to compete.
Almost all winners of Dansk Melodi Grand Prix have gone on to represent Denmark at Eurovision; the only entry not representing Denmark at Eurovision being the 1996 winner ("Kun med dig" by Dorte Andersen and Martin Loft), which failed to qualify for the final from the pre-selection. Denmark has won Eurovision three times: in 1963, 2000 and 2013.
The following table lists those entries which finished fifth or higher at Eurovision: