Cuper's two-year tenure, thus, came to a bitter end, with just a Spanish Super Cup to show for his efforts, and the supporters were hardly sorry to see him go.
However, the appointment of Rafael Benitez as his successor hardly filled the fans with confidence.
Valencia president Pedro Cortes insisted that the man who had just taken Tenerife into the top-flight was the "ideal coach" for the club: "He's a professional who is highly qualified to take charge of the sort of team we want - young, aggressive and with a winning attitude."
It was common knowledge, though, that Valencia had offered the job to, and been rejected by, Javier Irureta, Mane Esnal and Luis Aragones.
Benitez's arrival didn't just surprise the supporters either; the squad was also taken aback. However, they were immediately won over by his mix of self-deprecation and self-belief.
According to Canizares, Benitez told them in one of his very first team meetings, "You come from the Champions League final and I come from Segunda Division, but, humbly, I think I have tools to make you improve."
And Benitez did just that, even though he was very nearly sacked less than five months into the job. The mastermind of 'The Miracle of Istanbul' has been very open about the fact that Valencia's 3-2 win at Espanyol on December 13 was one of the most important matches of his entire career.
The new boss was under intense pressure at the time, with Valencia having gone from second to eighth in the table after a run of five games without a win.
Therefore, the writing was on the wall for Benitez with his team two goals down at the break in Barcelona.
However, as happened in Liverpool's astounding fightback against AC Milan in 2005, the manager made a couple of crucial tactical tweaks that turned the game on its head, with Valencia running out victorious thanks to goals from Francisco Rufete (two) and Illie.
It was a victory which emboldened Benitez. "In January, I told several players that we were going to win the league," he told the club's media channel. "They thought I was crazy. But from that moment on, the team grew.
"A good job had been done previously by Hector Cuper. We gave it one more twist to make us a little more offensive-minded and balanced. Aimar was a very talented player who could perform much better when surrounded by hard-working players. Baraja got into the box better than anyone. There were players like Vicente or Kily who broke down defences.
"I think the team was very balanced. Everyone highlighted the partnership of Albelda and Baraja, which worked perfectly, but on the right with Rufete and Angulo, or on the left with Kily and Vicente, players who went back and forth and put in the defensive work. Quality is not only skill. Quality is doing the right thing at the right time -and we did it many times.
"Also, little by little, a great bond with the fans was forged, and Mestalla became strong. We had a lot of confidence that was growing day by day."
The net result was Valencia losing just one game between the tail end of January and May 11, 2002 as they romped to a first league title in 31 years, winning seven of their final eight games to finish eight points clear of Deportivo La Coruna.
"I will always remember the parade," Benitez told BBC Sport, "and seeing people crying in the streets."
It was, as the coach put it, "a glorious time" for Valencia and their supporters because, less than two years later, they won the title again, and this time it was complemented by a UEFA Cup success.
"It was a great year for all of the team, on an individual and collective level," Vicente told VCF Media Radio. "We did things very well and we were a very compact, solid team. Our defending was amazing, and when we went on the attack we were a very dangerous side. We were able to dominate sides and our counters were really good, getting a lot of people into the opposition box."
Valencia were also as strong mentally as they were tactically - unlike Madrid, their main title rivals for the majority of the season.
Florentino Perez's Galacticos were 12 points clear with 12 rounds remaining, but they eventually finished fourth after completely capitulating down the home straight. Valencia took full advantage as they embarked on a 10-game unbeaten run in which they took 28 points from a possible 30 to secure a second title in three seasons with two rounds to spare.
"I remember the celebrations in Valencia, with everybody in the Plaza del Ayuntamiento," Vicente said. "I'm Valencian, so seeing the city like that gave me goosebumps."
The players and the supporters were celebrating again 10 days later when Valencia defeated Marseille 2-0 in the UEFA Cup final in Gothenburg to seal a sensational double.
"This has been a great season," Benitez enthused that night in Sweden, "and we will set new targets for the next one."
However, he would be gone before it began.