While at Everton, new Danish national team coach Morten Olsen fully supported Gravesen and made him one of his pivotal players in the 2002 World Cup and Euro 2004 campaigns. His display in the 2002 World Cup qualifying game with Iceland, where Gravesen scored two goals in a 6–0 win, was so impressive that American boxer Mike Tyson asked for his shirt and wore it throughout his stay in Denmark. He played all four of Denmark's matches at the 2002 World Cup, though Gravesen and his partner in the Danish midfield duo, Stig Tøfting, justified their pit bull reputations when they ganged up to play a prank on teammate Jesper Grønkjær at a World Cup training session.