Going into the match the Tigers had netted only once in three Championship starts, but this match was over as a contest shortly after half-time as Sone Aluko, Abdoulaye Faye and Stephen Quinn all found the net at the KC Stadium.
Quinn made his presence felt after barely a minute of play, the former Sheffield United midfielder crossing well only for his effort to be taken well by Adam Bogdan in the Bolton goal.
The Tigers threatened again after seven minutes when Bogdan caught the ball again from a threatening centre by Ahmed Elmohamady.
Another ball into the danger zone, this time from Joe Dudgeon, met the head of Jay Simpson but the City striker's 12-yard effort sailed wide of the target.
Robert Koren was the next to try his luck for the hosts, but his free-kick from 25 yards was too high to trouble Bogdan.
The visitors were on the back foot in the opening stages but at last made their presence felt and Kevin Davies should have done better with a close-range header that failed to trouble City goalkeeper Ben Amos.
Keith Andrews' effort from 18 yards finally brought Amos into action as Bolton started to assert themselves, and their improvement was reflected on the scoresheet after 17 minutes when Chris Eagles netted the opener.
A free-kick from all of 35 yards left Amos flat-footed after the ball took a wicked deflection to give the Trotters the lead after 17 minutes.
A Zat Knight shot was blocked by Faye as Bolton went for their second, but it was Hull who registered next when Koren broke after 29 minutes and provided the assist for Aluko to strike his first goal for the Tigers following his summer move from Rangers.
The Tigers were now in the ascendancy and Knight had to display all his defensive prowess to block a right-footed drive from Simpson.
The hosts maintained their impetus after the break and had taken the lead within a minute of the restart. The Tigers were awarded a corner in their first attack of the half and from Quinn's flag-kick, Faye headed home his first for the club.
And it was 3-1 after 49 minutes when Quinn hit home from close range following more good work by the busy Simpson.
Koren then went close from distance as Bruce's men went for a fourth, Faye hitting the post following a Koren corner before Simpson also missed the target from 25 yards out.
At the other end, Benik Afobe had a shot blocked by Alex Bruce but Bolton were well beaten.