Two goals from Obafemi Martins and Steven Taylor, combined with the sending-off of Stephane Henchoz, in the space of nine frantic first-half minutes sent Newcastle on their way to back-to-back league wins.
Morten Gamst Pedersen's wonder goal gave the hosts renewed hope early in the second half, but Martins sealed the points for the visiting side with his second of the game deep into time added on.
Rovers started brightly and created two good opportunities in the early exchanges. On two minutes, Benni McCarthy was bundled over by Celestine Babayaro and from Robbie Savage's resultant free-kick, former Rover Shay Given was able to claim comfortably under pressure from Pedersen.
Four minutes later and the Norwegian winger supplied a brilliant first-time cross from the left, Peter Ramage failed to head clear and David Bentley fired over the bar off balance.
Rovers continued to dominate and were eager to get the ball forward as quickly as possible. On 13 minutes, Pedersen played in McCarthy, who lobbed Given from the edge of the box, but the goal was rightly ruled out for offside.
With a similar move, Nolberto Solano played the ball over the top to Martins, Andre Ooijer attempted to let the ball run through to his keeper, only for the Nigerian to collect the pass and fire a tame shot against the legs of Brad Friedel. From the resultant corner, Taylor's acrobatic effort was comfortable for the big American keeper.
A minute later, Ooijer's powerful header from Pedersen's corner was brilliantly saved by Given, before Rovers again had the ball in the back of the net.
Following Michael Gray's crossfield run, Shabani Nonda slipped in his strike partner, but after finishing well, McCarthy's effort was again correctly ruled out for offside.
Newcastle were next to get the ball in the net and this time the goal stood. On 31 minutes, Antoine Sibierski clipped the ball through to Martins and the Nigerian fired the ball high into the corner of the net with a crisp left-foot half-volley.
Buoyed by the goal, the visitors added a second just four minutes later. A corner from the right was only half cleared as two Rovers defenders got in each others' way, Charles N'Zogbia fired the ball back across goal from the far post and Taylor was on hand to blast home from close range.
And still the first-half drama wasn't complete, as, on 40 minutes, Martins headed past the covering Henchoz following a long ball upfield and after being dragged to the deck by the former Swiss international, referee Dermot Gallagher produced a straight red card.
Hughes made a double substitution at the start of the second half, with Andy Todd and Matt Derbyshire replacing Bentley and Nonda, and it appeared to have the desired effect.
On 47 minutes, Pedersen collected the ball on the left wing, before cutting inside James Milner and firing an unstoppable right-foot shot from fully 25 yards into the top left-hand corner of the net.
Despite being down to ten men, the momentum was back with the home side and just two minutes later, Tugay tested his luck from long range, forcing Given to palm clear at full stretch.
Rovers had much of the possession after the break, but just couldn't force a second opening. And as the home side through men forward, Newcastle always looked dangerous on the break.
On 61 minutes, Milner skipped past Gray, before firing straight at Friedel and with just six minutes remaining, Martins played a neat one-two with substitute Giuseppe Rossi, before dragging his shot wide when clean through on goal.
But as the full-time whistle approached, Rovers threw everyone up front, including keeper Friedel and man-of-the-match Pedersen was denied a deserved equalising goal by a brilliant Given save, before Newcastle struck on the break, with Martins skipping past the last man and slotting the ball home into the empty net.