Gravesen, clearly relishing his role as Everton's creative spark in place of Wayne Rooney, led the charge towards Bolton's goal and unleashed a fearsome attempt which beat Jussi Jaaskelainen but drifted wide.
The game became even scrappier as Bolton tried to halt Everton's onslaught with Duncan Ferguson finding himself singled out for a few stray elbows. The Scot, enjoying his first league start of the campaign, happily returned the favour.
Everton were caught with their eye off the ball in the 16th minute. Ivan Campo won a corner which was quickly taken by Stelios Giannakopoulos. Nigel Martyn managed to fist it away, but the clearance fell directly at Kevin Davies' feet and he drilled a low shot past four Everton players and into the net.
Gravesen, quickly emerging as the Merseysider's key play-maker, linked up well with Marcus Bent on the wing. He delivered a fine cross into the path of a diving Tim Cahill but his thunderous header fell a foot wide of the mark.
Everton delivered an important psychological blow to their visitors on the stroke of half-time when Kevin Kilbane's fancy footwork dazzled Gary Speed. He quickly skipped past the Welsh veteran before lofting a pass towards Ferguson who headed the ball just above Jaaskelainen's outstretched hand.
Davies put Bolton ahead for a second time when he snatched another opportunist goal from a rebounded shot in the 58th minute but just when Everton looked to be in real danger, they turned to Gravesen for salvation.
Bent won the home side a free-kick on the edge of the area. Gravesen mis-hit his effort but the referee controversially awarded Everton a second attempt because Bolton had not retreated the full ten yards.
This time, the Danish hit-man rocketed a low shot through the Wanderers wall and past a hapless Jaaskelainen to register his fourth goal of the season.
Not content with saving a point, Gravesen rallied his team mates as Bolton reeled from the sucker-punch.
Everton piled on the pressure in the final ten minutes, keeping Bolton captive in their own half and it paid off.
Picking the ball up on the edge of the box, Gravesen's shot took a cruel deflection off Radhi Jaidi in the 85th minute and it proved to be the final nail in Bolton's coffin.
MAN OF THE MATCH: Duncan Ferguson (Everton) - Won everything in the air and was always a menace to the Bolton defence on his first start of the season.