Gravgaard begon zijn loopbaan bij amateurclub Spentrup IF en brak door bij Randers Freja. Hij speelde voorts voor Viborg FF en FC Kopenhagen (Denemarken), FC Nantes (Frankrijk) en tot slot als huurling bij Hamburger SV (Duitsland). Met FC Kopenhagen won hij tweemaal de Deense landstitel.
Gravgaard speelde in totaal achttien officiële interlands (vijf goals) voor Denemarken. Onder leiding van de Duitse bondscoach Sepp Piontek maakte hij zijn debuut op 17 augustus2005 in de vriendschappelijke wedstrijd tegen Engeland (4-1). Gravgaard viel na 45 minuten in voor Per Nielsen en nam prompt het derde doelpunt van de Denen voor zijn rekening. Op 2 juni2007 greep Gravgaard in, toen een fan het veld bestormde en op weg was naar de Duitse scheidsrechter Herbert Fandel in het EK-kwalificatieduel tegen Zweden. Het duel werd vervolgens stilgelegd en afgebroken.
FC Kopenhagen