The qualification was a knockout tournament where the teams would play on a home-and-away basis. It consisted of a preliminary round, a round of 16, and a quarter-final round. The four quarter-final winners would qualify for the tournament proper; one of those four countries would then be chosen to host it.
In fact, a few first round matches took place before the preliminary round games. The first ever European Nations' Cup qualifying match was played on 28 September 1958 between the Soviet Union and Hungary. The first ever goal was scored by Anatoli Ilyin 4 minutes into that game. On 3 December 1958, Greece became the first team to ever be eliminated from the European Nations' Cup.