The Millers headed into the game full of confidence after recording two wins on the bounce under their new boss Matt Taylor, but they were swept aside by their neighbours from East Yorkshire.
Hull were the first to threaten with Greg Docherty flashing an effort across goal from the edge of the box.
The same player was then slipped in to an identical position by Jacob Greaves, but this time his shot was tipped wide by Viktor Johansson.
Dimitrios Pelkas fired over from the resulting corner after receiving Jean Michael Seri's low ball.
Hull were completely in the ascendancy in the first 20 minutes and again forced Johansson into action when Pelkas dispossessed Wes Harding and fired in a shot from the edge of the box.
Ben Wiles had looked the most likely to break the deadlock for the home side and he drew a tremendous save from Nathan Baxter after catching a volley powerfully.
Hull's pressure finally paid off after 44 minutes when Greaves was on hand to poke the ball home after a melee in the box following a corner.
But it was to prove a short-lived lead with Dan Barlaser lashing in a curling effort two minutes into added-time to level the scores at the break.
Hull came out lively again for the second period and twice forced Johansson into saves. The first was from a free-kick by Pelkas and then Regan Slater tried to power the ball in from a tight angle.
They were back ahead after 52 minutes when Cyrus Christie skipped down the right-hand side before firing low beyond Johansson.
Docherty was then sent through on goal but - after breaking clear of the Rotherham defence - could only fire straight at Johansson.
Hull's lead was extended just before the hour mark with Rotherham absolutely cut apart by a sweeping move.
Seri picked out Greaves with a stunning low ball and the skipper laid on a perfect cross for Ryan Longman to slot in.
Slater almost made it four but his shot was clawed out by Johansson after Christie had again wriggled down the right-hand flank.
Oscar Estupinan also came close to extending the lead but he headed the resulting corner wide.
Hull continued to search for another and Ozan Tufan came close with a long-range drive before sealing victory five minutes from time. He was put clear by Brandon Fleming and slipped his effort beyond Johansson.
Estupinan really should have added his name to the scoresheet too but he blazed the ball over from close range.
Rotherham reduced the deficit at the death with Georgie Kelly on hand to tap in from Tom Eaves' cross.