Pedersen played the position of inside forward for AIA but was moved out as an outside winger when representing the Danish national team. He was a box-to-box midfielder, often making last-ditch saves as a defender before sprinting the length of the field to participate in attacking moves. He was a quick player with great sportsmanship. Pedersen made his debut for the senior Danish national team in a 1952-55 Nordic Football Championship game against the Sweden national football team on June 21, 1953. In his sixth national team game on July 3, 1955, Pedersen scored his first two international goals, as Denmark beat the Iceland national football team 4-0 in a friendly match. By 1958 he had become national team captain, a position he governed in 16 games before Poul Jensen was made captain in 1960.
At the 1960 Olympics, Pedersen played in the position of right winger on the Danish team, often linking up with right halfback Bent Hansen. Pedersen played all five games as Denmark won the silver medals. During the tournament, he scored the winning goal in the 2-1 group stage win against the Poland national football team. After the Olympic tournament, Pedersen only played five additional games for Denmark. On September 17, 1961, he broke Pauli Jørgensen's record from 1939, as Pedersen became the first Dane to play 48 games for the national team, when Denmark beat the Norway national football team 4-0 in a 1960-63 Nordic Football Championship game. Later that month, Denmark lost 1-5 to the West Germany national football team and Pedersen's international career underwent a three-year hiatus. On September 6, 1964, Poul Pedersen made a one-game international comeback, thereby becoming the first Dane to play 50 international games; a record that was broken a few months later by Bent Hansen in November 1964.