[1] The qualification was a knockout tournament where the teams would play a two-legged tie on a home-and-away basis.

If the aggregate scores were level at the end of the tie, a third leg was played at a neutral venue to decide the winners.

17 teams entered the competition; notable absences included West Germany, Italy and England.

The first European Nations' Cup qualifying match was played on 28 September 1958 between the Soviet Union and Hungary.

On 3 December 1958, Greece became the first team to be eliminated from the European Nations' Cup after losing 8–2 on aggregate to France.