In many or most current sports events, teams or even individual athletes are classified by their nationality. Did this nation vs. nation aspect originate with the modern Olympic Games in 1896 or were there already inter-nation matches prior to them?
It was a little earlier than that. Rowing was a very popular sport in the nineteenth century. The nationality of the individual rowers or boat crews was always mentioned in contemporary newspaper accounts of the big races. They were big races too. In 1869 50,000 fans lined the Thames river to watch the Harvard team compete against the Oxford team in what was billed the "First International College Rowing Championship." Oxford won that race. The annual Oxford-Cambridge boat race at Putney on the Thames soon expanded into an international regatta. Columbia University of New York City won that race in 1879. Professional rowers in one man sculls became internationally known superstars, earning enormous amounts of money from races that could attract crowds as large as 150,000 people for the biggest races. Ned Hanlan from Toronto Canada and Edward Trickett from Australia were the two biggest rowing superstars in 1880.
The Federation Internationale des Societies d'Aviron was established on June 25 1892 and the first European Rowing Championship was organized in 1893. Like modern day Formula 1 auto racing, the 1893 Rowing Championship set up a series of regattas in France, Belgium, the Netherlands, Great Britain, Germany, Switzerland and Italy.
Source: The history section of the FISA web-site
http://www.rowinghistory.net/1869.htm
To extend upon OP's question.
Were the modern olympics games a phenomena of the long 19th Century? Was it nationalism which facilitated the creation of the modern olympics?
Since the ancient Greeks thought of their polis as their nation because they were independent city-states, games like our modern Olympics have been going on since around 776 B.C. starting with the first Olympics in Olympia, Greece. There all the Greek poleis would have a chance to compete against each other in the events of chariot racing, wrestling and boxing called pankration, the 200 yard sprint (stadion), and the pentathlon (which was the stadion, wrestling, long jump, discus throw, and the javelin throw). There was also three other game sites in Greece where the Pythian, Isthmian, and Nemean Games where played where Greeks competed in these same events. The Pythian Games were played in Delphi in Northern Greece, the Isthmian Games were played on the Isthmus of Greece, and the Nemean Games where played at Nemea in Elis.
The Nemean Games were played every two years where Greeks competed for wild celery. The Isthmian games were also played every two years were Greek competed for pine leaves. The Pythian Games were played every four years for a garland of laurel and the Olympics were also played every four years for a garland of olive branches. So the act of representing a nation is something that has been going on throughout Greek history starting in the Archaic Period. The ancient Greek games scene is a scene that is much like book 23 in Homer’s Iliad when all of the Greek heroes compete for Patroclus’ armor. But yes this was a big deal for the Greek poleis because winning these games would get them extreme honor, or arete not only in their poleis, but around the Greek world. Plus, the religious reasons for playing in these Panhellenic games to praise Zeus (Olympics), Poseidon (Isthmian), Pythian (Apollo), and Nemean (Heracles/Zeus) was a big deal for each Greek. So for religious reasons especially, the ancient Greeks felt the need to represent their polis as best as they could so they could bring favor to their polis.
So in sum, ancient Greeks were definitely training to represent their nation, or polis, in each of these games to bring their polis glory, much like our athletes do today for their country. But the ancient Greeks had extra innovative when training and competing because they were doing all of these athletic to be noticed by the gods and gain favor from them.