Teams of the calibre of Inter Milan, PSV Eindhoven and Sevilla have also come a cropper at the Sukru Saracoglu stadium this season but Chelsea's defeat was a huge surprise after the way they began the game.
The hostile atmosphere provided by their fans has undoubtedly played a part in Fenerbahce's impressive home record in Europe but the Istanbul crowd were soon silenced here.
Zico's tactic of pushing Fenerbahce's full-backs forward left Malouda and Joe Cole acres of space on the flanks in the early stages and it was from that route that the visitors' goal came.
Michael Ballack dummied the ball for Malouda to run down the left and his cross flew into the net after hitting Deivid's outstretched leg.
Fenerbahce did not learn from that setback and could easily have been 2-0 down within minutes when Essien strode forward unchallenged down the right and crashed a shot against the bar.
The chances kept coming for Chelsea too and Didier Drogba headed wide before he forced a great save out of Volkan Demirel from a tight angle.
Demirel did well again before the break when he beat Drogba to Ballack's through ball with the home defence again nowhere to be seen.
It seemed just a matter of time before Avram Grant's side got a second goal but instead, as the game wore on, Fenerbahce fought back.
Deivid grabbed a spectacular late winner for Fenerbahce
Their first chances of the game resulted in Alex heading wide when well-placed before Mateja Kezman tested Carlo Cudicini with an overhead kick.
And Chelsea looked less than convincing at the back even before Richards, who managed only one goal in the Premier League last season during an ill-fated spell at Sheffield United, came off the bench to play a key role in his side's fightback.
The former Bury and Brighton forward gave his side some much-needed energy up front alongside the lethargic Kezman and his pace also played a part in their equaliser.
Richards ran clear to meet Aurelio's lobbed through ball and power his shot past a helpless Cudicini.
That clearly rocked Chelsea and suddenly they were the side looking vulnerable, while Fenerbahce poured forward.
Grant's side seemed to have weathered the storm, however, and they threatened again through Ballack before Deivid turned from villain to hero in dramatic style with nine minutes left.
The Brazilian picked up the ball 30 yards from goal and considered his options before unleashing a thunderous strike that flew past Cudicini and into the roof of the net.
Credit must go to Zico for masterminding his side's recovery but Chelsea's first defeat in Europe adds fuel to the fire for those who doubt Grant's ability in big games - and leaves the Blues boss with plenty to think about ahead of next Tuesday's second leg.
E-mail this to a friend 
Printable version 
News conference: Chelsea boss Avram Grant
Bookmark with:
What are these?