Goals from Robert Koren and Aaron Mclean lifted the air of frustration which had descended on the KC Stadium after the Tigers somehow went in at the break trailing.
Chris Wood celebrated his 20th birthday with a gift-wrapped goal to open the scoring 11 minutes before half-time despite the hosts' dominance.
But Barmby's men, spurred on by the virtuoso performance of winger Cameron Stewart, levelled the scores early in the second half before Mclean's fortuitous 67th-minute winner, which left ex-Hull goalkeeper Boaz Myhill red-faced.
Even the weather could not match the frosty reception given to former Hull loanee Marlon King on the striker's return to East Yorkshire. His every touch was jeered, but his failure to control Chris Burke's early searching pass was well received by the home fans.
It was Chris Hughton's side who created the first chance, Wade Elliott's near-post corner finding Wood whose header was beaten away by Peter Gulacsi in the eighth minute.
The hosts responded with some patient build-up play which allowed Koren to test Myhill with a long-range drive. Stewart's corner then found James Chester in space but his downward header bounced up and over the bar.
Blues survived a penalty shout when Pablo Ibanez appeared to bring down Matty Fryatt in the box, with referee Michael Naylor unmoved by Hull's appeals.
Corry Evans had the home crowd on their feet midway through the first half with a fizzing first-time volley which flashed just wide.
Fryatt hit the side-netting moments later as caretaker manager Barmby saw his charges control the opening exchanges. And yet they were nearly undone when Elliott ran onto Burke's through-ball before firing his shot straight at Gulacsi.
Stewart's powerful low drive just three minutes later was a reminder of the threat he posed, with Stephen Carr struggling to contain the former Manchester United youngster.
Stewart soon pushed forward again, cutting inside unopposed to tee up Koren, who drilled narrowly wide from just outside the area.
With 34 minutes gone, and firmly against the run of play, Wood lashed King's short pass into the bottom corner from just inside the area for his 10th goal of the season and first in 11 matches.
The final chance of the half fell to Stewart, but his floating effort curled just wide of the far post.
Within 90 seconds of the restart, Hull's frustrations dissipated and it was, unsurprisingly, Stewart who unlocked the door. His teasing delivery was deflected into the path of Koren, who volleyed past Myhill from around the penalty spot.
Birmingham struggled to respond to the setback and could have gone behind just before the hour mark when Jack Hobbs nodded Koren's right-wing corner over the bar.
Mclean delivered the victory the home side's performance deserved after latching onto Koren's pass - but Myhill, who spent six-and-a-half years with Hull, should have kept his low near-post shot out with ease.
The visitors could have snatched a point but Gulacsi thwarted Burke's close-range header before substitute Guirane N'Daw put a late headed effort over the bar.