Olsen made his debut for the Denmark under-21 national team in September 1970, scoring a single goal in a 2–2 friendly match draw with the Poland U21s. Three weeks later, he was called up for the senior Danish national team under the Austrian national team manager Rudi Strittich, and Olsen made his national team debut in September 1970 against Norway. He played his first national team game as a right winger, but eventually settled as a defensive midfielder. He helped Denmark qualify for the 1972 Summer Olympics, but could not participate at the tournament, as he had signed a professional contract with Cercle Brugge beforehand.