Ole Gunnar Solskjaer's side were seen as relegation certainties heading to St Mary's, yet they secured an invaluable 1-0 win against the odds.
This was just Cardiff's third league victory in the last four months and saw the Barclays Premier League's worst travellers secure just their second win on the road this term.
It was the perfect response to the controversy surrounding claims in the build-up that last week's team that lost 3-0 to Crystal Palace had been leaked to their opponents.
The Welsh side looked set to suffer a similarly large defeat at St Mary's after a woeful first half in which Gaston Ramirez rattled the crossbar.
However, wayward finishing and a fine display from goalkeeper David Marshall kept the hosts at bay, allowing the away side to sneak an improbable win from a surprising source.
Having failed to clear their lines, Cala - one of four changes from last weekend's embarrassing loss - showed poise and skill few would expect from a centre-back to strike home from the edge of the box.
Mauricio Pochettino's side pressed for a late leveller but it was not to be as they failed to score for just the sixth time this season, giving Solskjaer's men a huge three points.
Saints made one change for the match as Ramirez came in for the injured Jay Rodriguez, who the hosts' players showed support for in the warm-up by wearing training shirts with the number nine on the back.
The in-form forward's absence did little to stop Southampton's attacking flow, though, and Cala had to be alert early to prevent an early Luke Shaw cross being tucked away.
The Spanish centre-back did well to deny Adam Lallana soon after and Fabio deflected a Steven Davis cross behind as Cardiff were pinned back.
Peter Whittingham attempted to catch out Saints goalkeeper Paulo Gazzaniga from a free-kick in a rare moment of respite for the visitors.
Lambert headed over at the far post as Saints upped the ante, with Ramirez hitting a fizzing effort which rattled the crossbar after taking a slight deflection off Steven Caulker.
Marshall did well to claw away a 22-yard free-kick from Lambert as the hosts continued in the ascendancy, with pair going head-to-head again when the England forward wriggled free to prod goalwards.
Referee Jon Moss waved away appeals for handball against Caulker as half-time approached, before which Whittingham attempted to catch Gazzaniga out direct from a corner.
The Argentinian goalkeeper, playing due to injuries to Artur Boruc and Kelvin Davis was clearly being targeted at set plays but City were struggling unsettle him.
Solskjaer brought on Wilfried Zaha early in the second half in a bid to add a new attacking dimension to a Cardiff side, who only had a Jordon Mutch effort from distance to show for their endeavours in the 15 minutes after the restart.
Morgan Schneiderlin and Ramirez had shots blocked in that time as Saints continued to dominate, with Lambert nodding over a fine Calum Chambers cross.
Ramirez comically collapsed in a heap when trying to control a Jack Cork ball over the top - a let-off for Cardiff given the Uruguayan playmaker was clean through.
It was the latest in a long line of missed opportunities that the home side were made to rue in the 65th minute.
Having failed to clear their lines, Cala took the loose ball on his chest, jinked free and unleashed a wondrous left-footed drive past Gazzaniga to the delight of 2,404 travelling fans.
Nathaniel Clyne and Sam Gallagher came on as Saints looked for a response, with the latter quickly in the action.
Having just failed to meet a Lambert header, the teenager soon collected a chipped ball from Schneiderlin - only to be denied by Marshall.
The Scotland international came under increasing pressure as the clock wound down and denied Clyne by wonderfully tipping wide.
Guly do Prado failed with a tame header and Lambert miscontrolled the backpost as the clock wound down, leaving gaps at the back.
Zaha showed great skill and strength before being denied by Gazzaniga late on, but it mattered little for Cardiff as they held out for victory.