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 matches of the first round took place before the preliminary round matches. 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 of the Soviet Union four minutes into that game. On 3 December 1958, Greece became the first team to ever be eliminated from the European Nations' Cup after losing 2–8 on aggregate to France.