La nazionale greca fece il suo esordio nel 1906 ai Giochi olimpici intermedi di Atene. Nel 1919 partecipò ai Giochi Interalleati, organizzati a Parigi dopo la fine della prima guerra mondiale, e poi al torneo olimpico di Anversa 1920, prima edizione riconosciuta come ufficiale dalla FIFA. In questi anni una figura chiave fu quella di Giōrgos Kalafatīs, giocatore e poi allenatore della squadra. La federazione calcistica della Grecia si affiliò alla FIFA soltanto nel 1926. Nei decenni seguenti la nazionale greca non conseguì alcun risultato di rilievo, anche a causa dei problemi socio-economici del paese prima e dopo la seconda guerra mondiale. Fino agli anni ’60 gli ellenici rimasero, infatti, ai margini della scena calcistica, al pari delle vicine squadre cipriota e maltese (con le quali sussiste un’accesa rivalità). Soltanto l’apertura agli allenatori stranieri diede un impulso al calcio greco, nonostante i risultati rimanessero mediocri. La Grecia andò vicina alla qualificazione al campionato del mondo 1970. La compagine, che annoverava alcuni tra i migliori calciatori greci di ogni epoca quali Dīmītrīs Domazos, Giōrgos Siderīs, Giōrgos Koudas e Mimis Papaioannou, si piazzò seconda nel suo girone di qualificazione, a un solo punto dalla Romania.
Il primo traguardo di rilievo fu la qualificazione al campionato d’Europa 1980, ottenuta davanti all’Unione Sovietica e all’Ungheria. Allenata da Panagoulias, la Grecia si presentò al torneo – ospitato dall’Italia – come la possibile rivelazione, dopo aver vinto il proprio il girone di qualificazione contro avversarie molto quotate, Unione Sovietica e Ungheria. Nella fase finale uscì, però, al primo turno, collezionando due sconfitte (1-0 con Paesi Bassi e 3-1 con la Cecoslovacchia) e un pareggio a reti inviolate contro la Germania Ovest, poi vincitrice del titolo.
Dopo la partecipazione al campionato d’Europa del 1980, si verificò una lunga assenza della Grecia dal palcoscenico internazionale di rilievo, interrotta con la qualificazione al campionato del mondo 1994 negli Stati Uniti d’America: gli ellenici ci arrivarono da primi classificati nel proprio girone eliminatorio, battendo e superando all’ultima giornata, il 17 novembre 1993 ad Atene, la Russia (anch’essa qualificata) con gol del ventenne Nikos Machlas e non patendo alcuna sconfitta[5]. Dal 1992 l’allenatore era di nuovo il sopraccitato Alketas Panagoulias[3], già CT della nazionale nei periodi 1973-1976 e 1977-1981. Come nel 1980, anche nel 1994 il cammino dei greci nella fase finale non andò oltre i gironi. La Grecia perse tutti gli incontri: per 4-0 contro l’Argentina e la Bulgaria (con Batistuta e Stoichkov autori di triplette) e 2-0 contro la Nigeria.[3] Curiosamente, nel corso del torneo, la compagine ellenica impiegò tutti e tre i portieri disponibili, eventualità piuttosto rara.