England were forced to work hard to beat New Zealand's modest total of 205 and secure their first victory since arriving in Australia in early November.
Man-of-the-match Flintoff hit 72 not out off 75 balls but there were anxious moments for England who reached the required 206 runs with one ball to spare at Bellerive Oval on Tuesday.
When Ian Bell fell for 45, England was 138-5 and the game was in the balance. But Flintoff and Paul Nixon (15) put on 60 to guide their side to within eight runs to win before the latter was run out.
With 17 balls to go, victory seemed a formality, but New Zealand clawed their way back, leaving England chasing four runs in the last over and nervous tail-ender Jon Lewis on strike against part-time seamer Craig McMillan.
Lewis picked up a single from the second ball of the over, before Flintoff picked up two runs from the next delivery and then fittingly hit the winning runs with a straight drive from the second-last ball of the match.
The victory was a welcome relief, but wasn't all good news for England though, with captain Michael Vaughan appearing to strain his left hamstring in his second game back from a long absence after knee surgery.
Opener Vaughan made 17 and had to bat with a runner late in his innings.
Flintoff, who also bowled impressively, batted with more restraint than usual and survives some anxious moments as the victory loomed.
In the 45th over, Flintoff just cleared New Zealand fieldsman Ross Taylor on the mid-wicket boundary from the bowling of Daniel Vettori.
With the game in the balance, Taylor was in a few metres from the fence and got a hand to the ball as he retreated, but it went for four.
In the 47th over, Flintoff was caught at mid-on from the bowling of Mark Gillespie, only for square-leg umpire Steve Davis to rule the waist-high full toss a no-ball.
The tight bowling of young Kiwi spinner Jeetan Patel, who took 2-34 and also fielded brilliantly, forced England to work hard for the win.
Earlier, seamer James Anderson took four wickets to give England an excellent chance of breaking their two-month drought.
The English enjoyed the absence of their nemesis Australians and stifled the Kiwis, who began their innings intending to capitalise on the fragile mindset of their opponents.
There were ominous signs for England when the second ball of the innings was lofted for six by Kiwi opener Brendon McCullum and the fourth ball saw a horrible fielding error by Anderson turn a single into a four.
However, Anderson went from villain to hero with a superb opening spell that put his side on top, before part-time seamer Paul Collingwood and spinner Monty Panesar strangled the New Zealand batsmen during the middle overs of the innings.
Anderson set the tone with a superb opening spell in which he generated good pace, swung the ball both ways and claimed three vital wickets to rock the Black Caps, who had won the toss.
His claimed the wickets of McCullum, New Zealand captain Stephen Fleming and Taylor and New Zealand never recovered, with none of their batsmen able to compile a meaningful innings.
Anderson's first spell netted 27-3 from his eight overs and he finished with 42-4, bowling Mark Gillespie with the final ball of the innings.
His early good work was ably backed up by Collingwood (25-2), Panesar (36-1) and Flintoff (37-2).