Having taken only a point from their opening three games, the mood was low at the Tigers but Jackson Irvine's double and Fraizer Campbell's effort lifted spirits at the AESSEAL New York Stadium.
The Millers had gone in front through Richard Wood, and then made a game of it when Jamie Proctor scored, but Paul Warne's men have now lost three out of their opening four matches since returning to the Championship after a year in League One.
Despite the negativity surrounding the club, the Tigers started the better and had two openings in the first 15 minutes.
First Markus Henriksen brought a flying save out of Marek Rodak with a swerving effort from distance and then from the resulting corner Daniel Batty's rasping drive was blocked by Wood.
The Millers captain was in the thick of the action and in the 16th minute he gave his side the lead as he powered home Ryan Manning's corner after some slapdash defending from Reece Burke.
It was almost two as Manning ran on to a loose ball and curled a first-time effort just wide, but within a minute Hull were level.
Evandro found some space on the right and curled in a perfect cross for Irvine, who had even more space at the far post to convert.
Hull chose the perfect time to go ahead as they scored again in first-half injury time, when Campbell rolled home from close range after Rodak misjudged his punch.
Nigel Adkins' men were in dreamland two minutes after the restart as they went further ahead. Campbell dispossessed Semi Ajayi, fed Jarrod Bowen who laid it on a plate for Irvine to slot home his second.
Irvine had the chance to earn a hat-trick when he fired over from 12 yards out and Hull could have done with that hitting the back of the net as Rotherham began to build some momentum.
They got back into it with 15 minutes remaining when Proctor headed home from Zak Vyner's cross.
Hull had some defending to do and the Millers had enough chances to take something out of the game as Richard Wood headed straight at David Marshall and Will Vaulks dragged a shot wide.
Their golden chance came in added time, but they were unable to take it as Ajayi headed over from a fine position and Hull enjoyed a much-needed victory.