A tense and closely-fought opening half saw Rhys Patchell and Paddy Jackson exchange kicks as Ulster took a slender 12-9 lead into the half-time break.
Blues enjoyed plenty of possession in the second period but could not break through a well-drilled Ulster defence.
And tries from Tuohy and an intercept score form Humphreys saw Blues suffer a second home defeat of the campaign in the Guinness PRO12.
A promising start from the hosts saw scrum half Lewis Jones charge down a kick from opposite number Paul Marshall as the home side looked to make a quick start and tested Ulster around the fringes.
The Irish side produced a big response as returning winger Tommy Bowe almost exploited a gap in midfield as Blues unlocked tackle after tackle in a breathless opening five minutes.
The first scrum of the game saw Ulster win the first penalty of the night, as the Blues front row popped up, and Paddy Jackson slotted the resulting kick for the lead.
Obstruction stopped a jinking Adam Thomas in midfield and Jackson kicked to the corner as Ulster looked to turn up the heat in the opening period. A powerful driving maul had some success, but as Ulster looked to go wide the ball was spilled by Andrew Trimble.
Jackson looked to exploit any space out wide with a cross kick over Richard Smith with the home wide man alert to any danger.
Visiting scrum half Paul Marshall showed his skills to pick up a spitting kick from Gareth Davies and arch his run before neatly grubber kicking in behind as the game continued to be played primarily in the home half.
Prop Sam Hobbs produced an absolutely thundering tackle on Robbie Diack to rock the back row off his feet and fire-up the home crowd. But the resulting lineout was lost as Blues continued to try and build up a head of steam in the first half.
Lewis Jones broke clear and Ulster were forced to dig deep to stop a sudden Blues onslaught as Richard Smith, Alex Cuthbert and Matthew Rees all drove to the line. The penalty was secured and Rhys Patchell levelled the scores.
Some slick handling down the right from inside the 22 freed Cuthbert into space, but his chip ahead floated out on the full as he looked to take advantage of the space in behind.
Number Eight Nick Williams suddenly broke down field and sparked a bright Ulster attack that was kept alive with some quick handling before an on rushing Navidi flew out of the line and threatened an intercept only to spill as he looked to hold on to the difficult chance.
Spilled ball then lit up a Blues counter as Gavin Evans fed Patchell who showed his pace to slip past one tackler and offload before Ulster frantically bundled wing Smith into touch.
Livewire back Lewis Jones disrupted a scrum and Ulster were penalised for a man being offside as he picked up the loose ball. Patchell lined up the kick and from wide left slotted the ball over for a 6-3 lead.
The advantage, though, was short-lived as Vosawai was penalised at the breakdown by referee Neil Paterson and Jackson made no mistake to bring the teams level on the half hour.
Jackson added another four minutes later before Patchell followed suit. But it was Jackson who had the final word of the half with his fourth successful kick of the half for a 12-9 lead at the break.
Blues looked to up the tempo at the start of the second half, as the game continued to flow from end to end, with Darren Cave penalised for pulling a player back into the ruck to hand the home side a long range penalty. Patchell, though, pulled his kick wide left of the target.
Jackson also missed a difficult penalty chance to the left, but Ulster’s driving lineout was looking increasingly menacing. After shunting Blues back , Jackson opted for the corner and not the posts.
The decision was vindicated as Ulster went hard and strong down the middle and finally broke the resolve and through with lock Dan Tuohy finding the gap and brushing off tacklers to slide in under the posts.
Davies looked to kick-start Blues with a neat step and run inside his man. The forwards went to work before Matthew Rees and Davies combined and the ball was spun wide for Smith, but he juggled and lost the ball forward as the line closed in.
Blues were looking for a way to breakdown the Ulster rearguard, but the well-drilled visiting defence were snuffing out any opportunities. A big drive finally brought reward with Navidi marshalling from the back.
As boss Hammett started to empty his bench, Patchell turned down a kickable penalty and instead went for the corner to try and set up another drive. But Ulster again repelled the danger.
Only a last ditch tackle from Patchell stopped a marauding Michael Heaney before referee ruled out a try for a forward pass into the hands of Bowe.
Ireland international Bowe handed Blues a strong attacking platform when he failed to keep a clearing kick from Davies from going into touch. The home forwards battled away but the rock solid Ulster defence yet again held firm under a torrid examination.
Another big drive from Ulster took them into the corner as they looked to apply a killer blow. But Blues dug deep and forced the second drive back and forced the knock on from Marshall.
The decisive try did arrive five minutes from time as one pass too many in their own 22 was picked off by Humphreys and the conversion from the same player took Ulster away.
09m Jackson p 0-3
22m Patchell p 3-3
28m Patchell p 6-3
30m Jackson p 6-6
34m Jackson p 6-9
36m Patchell p 9-9
40m Jackson p 9-12
52m Tuohy t Jackson c 9-19
75m Humphreys t Humphreys c 9-26
Cardiff Blues: 15 Rhys Patchell (Walsh 78), 14 Alex Cuthbert, 13 Adam Thomas (Allen 67), 12 Gavin Evans, 11 Richard Smith, 10 Gareth Davies, 9 Lewis Jones (L Williams 56), 1 Sam Hobbs (Andrews 59), 2 Matthew Rees (R Williams 64), 3 Adam Jones (Filise 53), 4 Jarrad Hoeata (Cook 67), 5 Filo Paulo, 6 Josh Turnbull, 7 Josh Navidi, 8 Manoa Vosawai (Jenkins 61)
Replacements: 16 Rhys Williams, 17 Taufa’ao Filise, 18 Scott Andrews, 19 Macauley Cook, 20 Ellis Jenkins, 21 Lloyd Williams, 22 Cory Allen, 23 Geraint Walsh