The Whites were without a win in three games before Rovers arrived at Elland Road, but they were deserved winners against Sean O'Driscoll's side, who were decidedly fragile at the back.
Gradel fired them in front only for Billy Sharp to equalise just before half-time.
Franck Moussa gave Rovers an undeserved lead just after the break, but skipper Howson equalised soon after and further goals from Luciano Becchio, Gradel and Howson sealed a resounding victory for Simon Grayson's side.
Leeds made a bright start and they could have been in front just three minutes in but Rovers goalkeeper Gary Woods did well to deny Gradel from eight yards out.
Lively forward Gradel was proving difficult to handle and it came as no surprise when he opened the scoring after 11 minutes.
The tricky Ivorian turned sharply and jinked away from his man before driving the ball into the bottom-left corner of Woods' goal.
Leeds' sharp passing and movement was causing all sorts of problems for Rovers and after a flowing move Neil Kilkenny shot straight at a grateful Woods.
It was all one-way traffic and Robert Snodgrass seemed certain to give Leeds a deserved second goal but he lost his footing after rounding Woods and the ball rolled behind for a goal-kick.
And Leeds were made to pay for those misses on the stroke of half-time, when John Oster spotted Sharp's run and delivered a delightful throughball and, although Kasper Schmeichel blocked the diminutive striker's first effort, Sharp poked the ball home from a tight angle.
Snodgrass should have restored Leeds' lead three minutes after the break but fired wide of the far post.
And the Elland Road faithful were stunned less than a minute later when Dean Shiels nodded on for Moussa, who broke clear and beat Chimerical with a left-foot finish from inside the penalty area.
But Doncaster had barely finished celebrating when Howson fired in the equaliser.
The Leeds skipper won the ball in midfield and let fly with a right-foot drive from 22 yards which flew into the bottom-right corner.
Leeds were almost caught out moments later but Schmeichel thwarted Moussa from close range.
But Rovers were vulnerable at the back and Gradel was twice played through on goal but first slipped and scuffed his shot wide, then shot tamely straight at Woods with just the keeper to beat.
But Leeds were back in front with 16 minutes remaining when Leigh Bromby nodded down a Snodgrass cross into the path of an unmarked Becchio, who fired home from eight yards out.
Gradel gave Leeds breathing space eight minutes time when he fired home after Woods had denied Billy Paynter.
And Howson put the icing on the cake a minute from time when he raced clear and kept his composure before slotting past Woods.