A key moment came in the Copa America of 1999: Brazil were leading 2-1, but Mexico were piling on the pressure. And as the clock ran down, Brazil's coaching staff and substitutes were on their feet, pleading with the referee to blow the final whistle.
The Mexicans could hardly believe their eyes. Brazil were scared of them! Mexico lost the game but won plenty of self-respect. All through history, especially in that 1970 World Cup in their country, the Mexicans had looked up to Brazilian football as an almost untouchable reference. And now Mexico were able to lay a glove on the gods.
The population of Mexico is more than half of Brazil's, but it's over two and a half times that of Argentina. Mexico against Brazil has the potential to be Latin America's super-derby, and Tuesday's Olympic semifinal is another step on that path.
The tendency always was for the Brazilians to look down their noses at the Mexicans and their comparative lack of footballing tradition. In the Under-17 World Cup of 2005, members of the Brazil coaching staff were congratulating themselves after a thrilling 4-3 semifinal win over Turkey.
"We have just beaten the second best side in the tournament," one of them told me. It was an analysis that overlooked the obvious fact that earlier in the day Mexico had won their semifinal 4-0. When the two sides met in the final, it was an easy win for the likes of Gio Dos Santos and Carlos Vela over Marcelo and Anderson. Mexico won 3-0, and had a world title to their name.
The honours are still with Brazil in the one that really matters, the senior World Cup. The goal that Pele scored against Mexico back in 1962 may be the finest he ever managed in the competition, a masterclass of skill, balance and power. Closer to home, Brazil came out on top when the sides met in the second round of Russia 2018. The goalless draw between the teams four years earlier is every bit as important. Brazil had got off to an awkward start with a controversial win over Croatia in the opening game of their home World Cup. That could be put down to first night nerves. The second match would surely show the real Brazil.
But Mexico -- with keeper Guillermo Ochoa in fine form -- held them. There were whispers around the press box: "Is that all Brazil have got?" Doubts started to creep into the camp. It seems fair to argue that the slide towards that extraordinary 7-1 semifinal capitulation against Germany began a couple of weeks earlier against the Mexicans.
And, of course, Mexico can take heart from the final of the London Olympics nine years ago, when they hit the blocks fast and established a lead that Brazil were not able to peg back. Mexico now have their own tradition of winning titles against Brazil. And so there is no reason for them to be overawed going into Tuesday's semifinal. That same Ochoa is there to provide a last line of defence -- against a Brazil side who are fighting to get centre-forward Matheus Cunha fit in time.
Richarlison has scored most of their goals, but Cunha has been just as important, combining well and giving the attack a platform with his back to goal game that could be very interesting for the senior side. He grabbed the only goal of the quarterfinal against Egypt, but pulled up later in the game with a muscular problem. Brazil will miss him if he is absent, or even if he is not fully fit.
But it is at the other end of the field where things look most intriguing. With 14 goals in their four games, Mexico possess much more firepower than Brazil have faced so far in the tournament. Sevilla centre-back Diego Carlos has looked surprisingly weak defending against crosses, though he is classy on the ground. His partner Nino can be caught out against pace -- and the full-back on that side of the field is Daniel Alves, who was always more renowned for his attacking ability and intelligence than for the defensive side of his game.
This is an experienced Mexican side; most of them have played for the national team at senior level. They can also share the goals round -- seven players have been on target so far. With their midfield interplay and their pace down the flanks, Mexico are going to be asking some serious questions of the Brazil defence.
The short term question is simple; which of these teams will be contesting the gold medal match on Saturday? The longer term question is more interesting; where will this match leave Brazil vs. Mexico as it moves towards being one of Latin America's great footballing rivalries?