Solano put Newcastle ahead after just two minutes
Newcastle United's European campaign was ended by the away goals rule as the Magpies were held at home by Troyes in the Intertoto Cup final.
After the 0-0 draw in Troyes, the club from the champagne region of France produced periods of sparkling football to clinch a Uefa Cup spot in a game of extraordinary drama.
Newcastle took an early lead through Nolberto Solano, then found themselves 4-1 behind but managed to fight back to 4-3 with 20 minutes to go.
With the game deep into injury time Aaron Hughes headed the equaliser, but Troyes held on for the draw in one of the most remarkable games seen at St James Park for many years.
Newcastle threatened to blow the French visitors away with a storming start, and took the lead after two minutes.
Early storm
Robert Lee won the ball in midfield and Solano - back after missing the Premiership opener against Chelsea on Sunday - strode forward and rifled home a 25-yard drive.
However, as Newcastle's early storm blew itself out Troyes' passing game began to come into play.
Shay Given committed a howler against Chelsea on Sunday when he let Boudewijn Zenden's shot squirm through his legs.
And when Medhi Leroy let fly from 35 yards he could only palm the viciously swerving free-kick into the net.
Then it was the turn of Nicolas Gousse, who latched onto a poor defensive header, surged past Warren Barton and clipped the ball inside the far post.
Stunning fight back
The Toon Army was stunned into silence, and things got worse for the Magpies' passionate fans a minute into the second half when Warren Barton gave the ball away deep in his half.
Gousse hit the post and Samuel Boutal was on hand to bundle the ball home to make it 3-1.
Newcastle conceded a fourth on the hour when Boutal stole round the back to power a header past the helpless Given, but then came a stunning fight back.
Ameobi slammed home Newcastle's second after 64 minutes, and the coltish striker earned a penalty five minutes later.
Speed squeezed it under the keeper, and suddenly Newcastle had 20 minutes to keep alive their European dreams.
Aaron Hughes headed the equaliser deep into injury time, but the visitors held out to earn themselves a crack at the Uefa Cup in their first-ever European campaign.
Newcastle: Given, Barton, Dabizas, Hughes, Elliott, Quinn, Speed, Lee, Solano, Ameobi, Bellamy. Subs: O'Brien, Harper, Gavilan, Lua-Lua, Bernard, Acuna, Bassedas.
Troyes: Heurtebis, Boutal, Bradja, Hamed, Olivier Thomas, Leroy, Meniri, Rothen, Zavagno, Gousse, Saifi. Subs: Sekli, Djukic, Ghazi, Jbari, Edouard Thomas, Tourenne, Zambernardi.
Referee: F Treossi (Italy).