Federer last lost at the US Open against David Nalbandian in 2003
Roger Federer came through a desperately tense five-set encounter with Igor Andreev to keep his bid for a fifth straight US Open title alive.
The champion showed the frailty that has dogged him all year as he was taken to a fifth set but raised his game to win 6-7 (5-7) 7-6 (7-5) 6-3 3-6 6-3.
Andreev took the first set and had seven break points at the start of the second but Federer managed to hang on.
He will face Gilles Muller of Luxembourg in the quarter-finals.
Muller, a qualifier, stunned Russian fifth seed Nikolay Davydenko 6-4 4-6 6-3 7-6 (12-10) in a dramatic match.
Federer had looked superb in his third-round win over Radek Stepanek, but his recent frailties were in evidence throughout against Andreev on Arthur Ashe Stadium.
He broke me so easily at the beginning and I was struggling to get in a groove from the baseline
He made 60 unforced errors and faced 15 break points, and his survival was largely due to the fact that Andreev converted just two of them.
The Russian broke at the first attempt and should have taken the set from there, but he allowed Federer back in at 5-5 before edging the tie-break.
A nervous Federer then framed a smash to slip 15-40 down early in the second but Andreev failed to capitalise on five break points, and a further two in the next game.
Still the world number two struggled with his form, missing two set points in the second set tie-break before Andreev handed him the set with a wayward forehand.
That gave Federer a temporary boost and when he cracked away a cross-court forehand to break for 3-1 in the third, the game appeared up for Andreev.
But at the same stage in the fourth set Andreev benefited from a hugely fortuitous net cord and confidently served out to take it to a decider.
At last, Federer reminded everyone of why he has won 12 Grand Slams as he stepped up a gear, moving 3-0 clear after winning an epic rally to break.
It was hardly downhill all the way after that as the Swiss fought off four break-back points at 4-2, but his fighting spirit saw him through to a meeting with Muller,the world number 130.
"He was playing well," Federer said of Andreev. "He broke me so easily at the beginning and I was struggling to get in a groove from the baseline.
"The second set was key for me to get back in the match. I served well but it was a tough match."
Davydenko could not cope with Muller's serve-volleying and a barrage of 20 aces on Louis Armstrong Stadium.
Muller pulled out his best shots when it mattered, serving an ace to save a set point at 4-5 in the fourth set and saving another with a big serve at 6-7 down in the tie-break before getting a net-cord on match point.
"I think it's not about that last point," said Davydenko. "It's about many points. I had so many chances."
In the same half of the draw, third seed Novak Djokovic edged out Tommy Robredo 4-6 6-2 6-3 5-7 6-3.
The Serbian will play American Andy Roddick in the last eight after the 2003 champion thrashed Fernando Gonzalez 6-2 6-4 6-1.