They have challenged for regional glory at the AFF Championship, vied for medals at the Southeast Asian Games and even done battle in a quest to qualify for the FIFA World Cup.
Even in less high-profile contests, bragging rights have always been offer for two football-mad nations in close proximity.
But when Indonesia and Vietnam renew their rivalry once more on Friday, the stakes have perhaps never been higher.
Especially when a place in the knockout round of the AFC Asian Cup is potentially up for grabs.
Not that success on the Southeast Asian stage does not -- or no longer -- matters.
For almost all of the region, that remains the most realistic avenue to silverware at the moment and, even then, many have now recognised that cannot be the ceiling to their ambition.
The Asian Cup represents the next level.
And after both suffered defeat in their opening games at the ongoing edition, Friday's Group D encounter between the familiar foes is looming as a must-win encounter.
It certainly is a tie neither can afford to lose, and a draw will do little good as well.
In a tournament where finishing third could still be enough to book a knockout-round berth, three points would be a healthy haul.
So with powerhouses Japan and Iraq expected to take the top two spots in Group D, Indonesia and Vietnam's best chance of a win will come against one another.
Adding further intrigue to what is already always an eagerly-anticipated affair is that both teams will have reason to believe they can emerge victorious on Friday, based on their opening displays.
Vietnam gave Japan an almighty scare when they overcame an early deficit to lead 2-1 by the 32nd minute, putting them on course for what would have been one of the biggest upsets in tournament history.
While Japan ultimately managed to regain their footing and claim a 4-2 victory, they never had it easy against their last-illustrious opponents.
What would have been particularly pleasing to Vietnam coach Philippe Troussier was the endeavour and adventure his charges displayed, even if this was not -- on paper -- their strongest XI in recent memory.
Star playmaker Nguyễn Quang Hải and defensive stalwarts Đỗ Duy Mạnh and Vũ Văn Thanh were all left on the bench, while regular national team features from previous years such as Đặng Văn Lâm, Nguyễn Tiến Linh and Quế Ngọc Hải are all not even at the tournament.
Troussier's starting lineup against Japan averaged just 16 caps - with captain Đỗ Hùng Dũng the sole member who featured at the last Asian Cup.
Yet, despite their lack of big-game experience, Vietnam were able to rise to the occasion.
The same can be said of Indonesia in their 3-1 loss to Iraq, where they constantly threatened with some fluid counterattacking and even managed to draw level after the opposition had edged ahead.
Having the youngest squad out of all 24 teams at the Asian Cup does not seem to be an issue for Indonesia, but this is a result of the work that has been done by coach Shin Tae-Yong since he took over 2020 -- as he brought through a generation of young talent that have now been playing together for a considerable amount of time.
Helping Indonesia's cause has been the introduction of several naturalised players with central midfield duo Ivar Jenner and Justin Hubner both giving an excellent account of themselves against Iraq.
But the star attraction is undeniably Marselino Ferdinan, who -- at the tender age of 19 - can now lay claim to being a scorer at the Asian Cup in addition to plying his trade in Europe with Belgium's KMSK Deinze.
There will be no shortage of exciting talent on display when Indonesia and Vietnam do battle on Friday and it truly promises to be a spectacle.
Both have and should continue to do Southeast Asian football proud yet, unfortunately in such a winner-takes-all scenario, it looks like only one can stand a good chance of going further come the end of the 90 minutes.