Shrewsbury Town scored their first Nationwide Conference victory away from home since 16 August with a controlled performance at Stonebridge Road.
Two clinical finishes from Ryan Lowe and a late strike from Colin Cramb secured all three points, as last week's FA Cup heroes turned in an off-colour performance.
An early effort from player-manager Jimmy Quinn was not to be typical of the best chances that Shrewsbury created - his shot being blocked by Fleet keeper Paul Wilkerson.
But the goal on 16 minutes was the pointer for things to come. A neat piece of trickery by Jamie Tolley released Lowe and as he advanced into the box he showed great composure to slide the ball to the right of Paul Wilkerson.
Both Tolley and debutant Duane Darby, recently signed from Rushden and Diamonds, provided good chances for Shrewsbury but both missed the target.
In a first half of few chances the best Gravesend could muster was a long-range effort by Steve Perkins.
Lowe and Sam Aiston provided Shrewsbury with width which always threatened to undo the Fleet defence but the red line held firm to the break.
The introduction of Ben Walshe, a recent flu victim, provided Gravesend with a more creative outlet in the second half.
Indeed a spell of three corners in quick succession lifted the home fans but their growing expectations took a knock on 64 minutes.
Player-boss Quinn had been replaced by Luke Rodgers and within two minutes of his arrival he raced onto a wide ball, checked, and gave the perfect pass for Lowe to score his second.
Although the third goal came in injury time no-one would deny that Shrewsbury did not deserve it, substitute Cramb breaking the offside trap to latch on to Greg Rioch's clearance and again beat Wilkerson.
The ease of the win was put into context by boss Quinn. "We expected Gravesend to be a threat but everybody did their job today and won their battles," he said.
Gravesend boss Andy Ford said: "Performances like that are a concern. We need to strengthen to try and make the gap in class that bit smaller."