Wales had been criticised, especially by coach Warren Gatland, for a slow start against South Africa a fortnight ago which ended in a 20-15 defeat.
But their Kiwi coach could have had few complaints as Wales came up hard, fast and - above all - disciplined in defence against his countrymen.
Ireland had managed a similar feat a week ago before fading to lose 22-3 but, unlike at Croke Park, Wales were then able to manoeuvre themselves upfield while keeping possession.
Richie McCaw could not resist the chance to slow down Welsh ball at a ruck, but referee Jonathan Kaplan was quick to spot and penalise him.
And Jones doubled Wales' advantage but, stung into action, New Zealand responded in thrilling fashion.
Nonu and Joe Rokocoko were part of a sweeping backs move that shredded Wales' first-up defence.
But although some good scrambling prevented a try, Martyn Williams went over the top at a ruck and Carter kicked New Zealand's first points.
The Canterbury fly-half should have drawn the Kiwis level on 20 minutes but his penalty kick - given away by Wales hooker Matthew Rees - rebounded off the post.
The home side again worked their way steadily upfield and a slipped inside pass from Shane Williams sent Jones haring towards the corner.
But New Zealand kept their line intact at the expense of a penalty that Jones dispatched to restore Wales' six-point lead.
The visitors' line was soon under threat again as Lee Byrne picked out lock Ali Williams in the middle of the Blacks' line and motored through.
Drawing opposite number Mils Muliaina, the Wales full-back flicked the ball behind him without checking where his support was and Brad Thorn snuffed out the danger.
New Zealand went to their forwards to help steady things and a more conservative approach earned steady territory and then a penalty in front of the Welsh posts.
Carter popped over the easy chance as the half came to an end, but Wales still held an encouraging 9-6 lead at the break.
Wales made a mess of the restart and gifted Carter an early chance to bring New Zealand level, the fly-half accepting the challenge.
Worse nearly followed as Powell fielded a kick but then gave Byrne the very definition of a 'hospital' pass, when the full-back was clattered by Richard Kahui as he received the ball.
New Zealand turned over possession and with Wales' full-back still buried under a ruck, a perceptive kick was chased towards the corner flag by Nonu.
Tom Shanklin just got there first but was forced to concede a five-metre scrum.
One back-row surge after a scrum was repulsed, then another, but at the third All Blacks scrum-half Jimmy Cowan was penalised for a crooked feed at the put-in and Wales survived.
But the pressure was relentless and eventually the Welsh defence ran out of numbers and Nonu was over, Carter adding the conversion.
Adding injury to insult, Wales lock Ian Evans damaged knee ligaments in the action and was helped off to be replaced by Luke Charteris.
Gatland also made a tactical change, swapping his half-back pairing as James Hook and Dwaye Peel came on, while opposite number Graham Henry sent on scrum-half Piri Weepu for Cowan.
Wales certainly needed fresh legs, their strength having been sapped by almost constant defence since half-time.
New Zealand were no longer being knocked back in the tackle and as a result were able to play their off-load game, gaining yet more ground and engineering another successful penalty kick for Carter to make it 19-9.
Wales had the chance to stem the tide when New Zealand infringed at a ruck, but Hook slid his first kick across the posts under the closed roof of the Millennium Stadium.
Carter had a more difficult chance to stretch the Kiwis' lead with 10 minutes remaining, opting to take on a monster kick from a metre inside his own half that plopped just wide.
But the fly-half made no mistake from his next attempt, tight on the left touch-line, to give New Zealand a 22-9 lead that was unlikely to be overhauled with five minutes remaining.
New Zealand finished off in style, hammering away at the Welsh line to see Kaino claim their second try at the death.
Wales: Byrne; Halfpenny, Shanklin, Roberts, S. Williams; S. Jones, Cooper; Jenkins, Rees, A. Jones, A. Jones, Evans, R. Jones, M. Williams, Powell. Replacements: Hook for S. Jones (59), Peel for Cooper (59), Charteris for Evans (57). Not Used: Hibbard, Yapp, D. Jones, Bishop.
New Zealand: Muliaina; Rokocoko, Kahui, Nonu, Sivivatu; Carter, Cowan; Tialata, Mealamu, Woodcock, Thorn, Williams, Kaino, McCaw, So'oialo. Replacements: Weepu for Cowan (55), Afoa for Tialata (49). Not Used: Elliot, Boric, Reid, Donald, Toeava.
Referee: Jonathan Kaplan (South Africa).
Assistant referees: Dave Pearson (England) and Cobus Wessels (South Africa).
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.