The Falcons handed maiden Premiership outings to summer signings Andy Perry and Tino Paoletti in the tight five, as well as former Sale man Elliott on the left wing who starred with two second half tries, while prop Robbie Morris entered the fray from the bench for his first competitive outing in a Newcastle shirt.
It was attack from both teams right from the start asthe Falcons pack mixed it up with a highly potent Sale eight, Colin Charvis and Cory Harris both forcing turnovers while Matt Burke kicked territory well and Jamie Noon fronted up in defence with some big midfield hits.
But it was Sale who opened the scoring when fly half Charlie Hodgson slotted a penalty from 40 metres out after Perry had pulled down a line out.
Midway through the first half the opening try finally came as Burke elegantly strode over in the right corner following a deep kick from Dave Walder, a knock-on from Cueto and a scrum just inside the 22 on the left wing. From good set piece ball Walder flung a wide pass to Burke, who powered through the gap for a score which Walder converted well from the touchline.
Hodgson erred with a penalty effort from the left, as did Walder, as a competitive half went on, with fierce battling for the ball at the contact area adding another dimension to the cutting back play.
Burke was taken out in mid-air by Sharks skipper Robinson although referee Tony Spreadbury controversially chose not to award a penalty, and moments later Sale took the lead when England wing Cueto touched down in the right corner after an off load from Jason White.
Hodgson was pressurised well by Hall Charlton, Phil Dowson and Cory Harris, who all claimed chargedowns, but the bounce of the ball just eluded the visitors at the vital moment as the Sharks went in as 10-7 interval leaders.
It was not long in to the second half when the Falcons reassumed their advantage, ex-Shark Elliott grubbering ahead down the right wing to score after a Jonny Wilkinson chip-and-chase and an offload from Charvis freed the flyer to break clear.
Wilkinson converted from the touchline, but two quickfire penalties from Hodgson saw Sale nudge two points ahead.
Wilkinson hit back on 53 minutes with a well-struck 40-metre penalty, while it was the turn of hooker Andy Long to charge Hodgson down, while Dowson and Geoff Parling both leapt to steal Sale line outs.
Midway through the half Hodgson turned predator when a Wilkinson pass fell behind its intended target, Mayerhofler, and Sharks centre Elvis Seveaili'i picked up the loose ball, popping to Hodgson who sprinted 40 metres for the try.
After another Hodgson penalty the Falcons got to within bonus point territory courtesy of a Wilkinson drop goal as Newcastle played a good advantage after Jason White had been dispatched to the sin bin.
Newcastle, camped in the Sale half, pressed for the crucial try Wilkinson breaking and offloading to Noon although the scoring pass proved elusive.
With stoppage time elapsed and in the last play of the game the Falcons went for broke, and having cultivated a two-on-one out wide courtesy of some powerful driving play, they earned their reward when Elliott crashed over in the left corner for his second try.
That left a touchline conversion from Wilkinson to win the game and, under a cacophony of boos from a Sale crowd not observing traditional rugby protocol, the crucial kick flew just right of the posts, as the final whistle sounded.
Edgeley Park duly erupted as the Guinness Premiership season kicked off in truly memorable style, with the Falcons' next test being a home match against newly-promoted Bristol next Sunday.
Tries: Cueto, Hodgson
Cons: Hodgson 2
Pens: Hodgson 4
Tries: Burke, Elliott 2
Cons: Walder, Wilkinson
15 Daniel Larrechea (Valentin Courrent, 80)
14 Mark Cueto
13 Mark Taylor
12 Elvis Sevealai'i
11 Jason Robinson (captain)
10 Charlie Hodgson
9 Richard Wigglesworth
1 Andrew Sheridan
2 Sebastien Bruno
3 Barry Stewart (Stuart Turner, 51)
4 Ignacio Fernandez Lobbe (Dean Schofield, 59)
5 Chris Jones (Chris Day, 40)
6 Jason White
7 Magnus Lund
8 Sebastien Chabal (Andy Titterrell, 70)
16 Andy Titterrell
17 Lionel Faure
18 Stuart Turner
19 Dean Schofield
20 Christian Day
21 Valentin Courrent
22 Robert Todd
15 Matthew Burke
14 Tom May
13 Jamie Noon
12 Mark Mayerhofler
11 Anthony Elliott
10 Dave Walder (Jonny Wilkinson, 40)
9 Hall Charlton
1 Ian Peel (Micky Ward, 53)
2 Andy Long (Matt Thompson, 73)
3 Tino Paoletti (Robbie Morris, 60)
4 Andy Perry (Stuart Grimes, 53)
5 Geoff Parling (Luke Gross, 75)
6 Phil Dowson
7 Cory Harris
8 Colin Charvis (captain)
16 Micky Ward
17 Robbie Morris
18 Matt Thompson
19 Luke Gross
20 Stuart Grimes
21 James Grindal
22 Jonny Wilkinson
Referee: Tony Spreadbury