Fu made three centuries and Trump two with the duo also making four breaks of 50 plus each in what is easily the finest match of this year's tournament so far before a thrilled crowd at the Alexandra Palace in London.
Hong Kong's Fu - who lost the 2011 final to Ding Junhui at the game's biggest invitational event - had trailed 3-0, 4-2 and 5-4 but made 80 and a closing 102 to secure a meeting with Mark Allen in the quarter-finals on Thursday with Trump left wondering how he lost.
"I've not played much better than this in my career," said world number eight Fu, who continued the level of form that saw him claim eight straight frames in a 9-4 victory over John Higgins in last month's Scottish Open final in Glasgow.
"It is one of the best wins of my career, especially the way it was going at the beginning to be 3-0 down to a top class player.
He played very well, and he didn't give it away. I think I earned it at the end so it has got to be one of the best victories of my career, definitely.
Judd Trump in action at the Masters.
Image credit: Eurosport
The match got off to a blistering start with Fu making breaks of 56, 67 and 130 only to find himself 3-1 behind at the mid-session interval in only 45 minutes.
Trump’s mind was focused from the outset as a break of 102 gave him the opening frame before an 87 cancelled out a 56 in the second with Fu breaking down on a black with a possible 147 on the table.
Trump sets up frame-winning clearance
A 67 eclipsed a 64 from Fu in the third frame as the scoreline quickly rolled to 3-0 with Fu’s stout 130 in the fourth vital to stem the bleeding.
[Marco Fu exclusive interview: 'It is heartbreaking and embarrassing that snooker can’t fund 128 players’]
He continued his revival with a fine run of 88 in the fifth frame to close the deficit to 3-2 in Trump’s favour.
Fu was among the balls in the sixth frame, but his failure to score heavily enough, a rare sight on such a day, resulted in Trump piecing together 79 to restore his lead to two frames at 4-2.
Fu's fabulous long red
Trump was first among the balls with a 53 in the seventh frame, but Fu was calmness personified as a clearing 58 saw him nick the frame on the black.
The recovery continued in the eighth frame as Fu showed the class that saw him reach the World and UK Championship semi-finals last year, and win the Scottish Open last month with an imperious break of 110 enough to restore parity at 4-4.
It was miss at your peril as a missed black by Fu in the ninth frame provided 2011 World Championship finalist Trump with the platform to piece together an immaculate 112 to move one frame up with a possible two to play.
Robertson punches the air after winning century break
The former UK champion looked set to complete the winning run, but missing a black off the spot on 36 produced another twist with Fu rolling in 80 to send the match to a deciding frame.
And Trump would fail to pot a ball in the 11th frame with another superb long red providing the platform for Fu's winning ton and place in the last eight.
In Tuesday night's match, 2010 world champion Neil Robertson was a 6-3 winner against Ali Carter as the Australian set up a quarter-final meeting with defending champion Ronnie O'Sullivan on Thursday afternoon, rounding off his victory with a break of 117 in the final frame.
"I was happy with that, all the hard work I've put in over Christmas paid off," said Robertson. "I played a fantastic match. Ali came back at me, but I finished it off in style when the score went to 4-3.
I'm looking forward to facing Ronnie, he's a wonderful player. It doesn't getting any bigger than that. It should be another great match as the crowd get behind him here more than they do in Sheffield. They get involved here, it is a great atmosphere.
"I'll be attacking, but I'll also have to compete with Ronnie on the safety side."
The 2012 Masters winner compiled runs of 85, 78, 69, 73 and a 117 in what was arguably his best performance of the season.
"I must be his favourite player to play against," said a dejected Carter. "He played out of his skin. It seems like I run into a brick wall every time I play him."
Latest results from first round
Judd Trump (Eng) 5-6 Marco Fu (HK)
103-1 (102), 87-56 (Trump 87, Fu 56), 67-64 (Trump 67, Fu 64), 0-134 (130), 11-118 (88), 79-36 (79), 63-68 (Trump 53, Fu 58), 0-110 (110), 112-5 (112) 36-80 (80) 0-124 (122)
Neil Robertson (Aus) 6-3 Ali Carter (Eng)
89-34 (85), 49-83 (83), 79-7 (78), 70-11, 102-14 (69), 0-73 (73), 0-93 (93), 73-0 (73) (117) 117-0
Desmond Kane at Alexandra Palace