Per la prima volta nella storia del Torneo olimpico, visto l'alto numero di squadre iscritte, venne stabilita una fase di qualificazione per ridurre il numero di partecipanti a 16, le qualificazioni al torneo di calcio della XVI Olimpiade si tennero fra il 23 ottobre 1955 e il 31 luglio 1956. Si iscrissero 24 squadre[2] (2 africane, 12 asiatiche, 8 europee[2] e 2 nordamericane) che si contesero 12 posti disponibili; ad esse si aggiunsero 4 squadre automaticamente qualificate alla fase finale: Australia (in qualità di paese organizzatore), Germania Ovest[2], Polonia e Turchia[2].
Queste qualificazioni furono le uniche a cui non presero parte le nazionali centroamericane e sudamericane e furono le uniche ad essere interamente organizzate e gestite dalla FIFA. Infatti, a Roma 1960 la FIFA gestì solo una parte delle qualificazioni, mentre a partire dalle qualificazioni a Tokyo 1964 l'incombenza è stata lasciata alle confederazioni ad essa afferenti.
Era previsto un unico turno ad eliminazione diretta con scontri di andata e ritorno dove le 24 squadre vennero abbinate su base geografica; Israele venne incluso tra le nazionali europee.
^abcdSul numero di iscritte vi sono delle controversie: alcuni sostengono fossero 24 (cfr. (EN) IX Olympic Football Tournament (Melbourne 1956), su linguasport.com. URL consultato l'8 dicembre 2023. e (EN) 1956 Melbourne Summer Olympics, su sport-olympic.gr. URL consultato l'8 dicembre 2023.), 12 delle quali si sarebbero qualificate alla fase finale ed a cui si sarebbero aggiunte Australia, Germania Ovest, Polonia e Turchia (qualificate automaticamente), per un totale di 16 nazionali. Altri invece sostengono che fossero 26 (cfr. (EN) Games of the XVI. Olympiad - Football Qualifying Tournament, su rsssf.org. URL consultato l'8 dicembre 2023.) e dunque - in questo caso - le qualificate alla fase finale sarebbero state 13 ed ad esse si sarebbero aggiunte Australia e Polonia (qualificate automaticamente), così da ottenere 15 nazionali. Non viene specificato in che modo sarebbe stata selezionata la sedicesima nazionale.
^Diverse fonti identificano questa nazionale semplicemente come "Vietnam" per questioni di eredità sportiva: l'allora Stato del Vietnam, comunemente noto come "Vietnam", si iscrisse al CIO nel 1952 (cfr. (EN) South Vietnam (VNM), su olympedia.org. URL consultato l'8 dicembre 2023.), ma nel 1954 - dopo la Conferenza di Ginevra - il Vietnam del Nord ottenne l'indipendenza e lo Stato venne scisso in due. Il CIO riconobbe solo il Vietnam del Sud come erede sportivo dello Stato del Vietnam e, dato che il Vietnam del Nord non si iscrisse mai al massimo organismo sportivo mondiale, in diversi continuarono ad usare l'epiteto "Vietnam" anche per riferirsi al solo Vietnam del Sud. Dal 1952 al 1972 fu esclusivamente quest'ultimo a partecipare ai Giochi olimpici (cfr. (EN) Vietnam (VIE), su olympedia.org. URL consultato l'8 dicembre 2023.).
Calcio
Mondo
.svg){kind=small}
.svg){kind=small}
Gran Bretagna
.svg){kind=small}
Filippine
.svg){kind=small}
.svg){kind=small}
Egitto
.svg){kind=small}
.svg){kind=small}
Corea del Sud
Thailandia
Taiwan
.svg){kind=small}
.svg){kind=small}
Afghanistan
.svg){kind=small}
.svg){kind=small}
Romania
.svg){kind=small}
.svg){kind=small}
Messico
.svg){kind=small}
Germania Est
.svg){kind=small}
Israele
Cambogia
.svg){kind=small}
Vietnam del Sud
Cambogia
Etiopia
Australia[13].svg){kind=small}
Polonia.svg){kind=small}
Squadra Unificata Tedesca[17]
Turchia
