Pierwszy oficjalny mecz międzypaństwowy reprezentacja Grecji rozegrała w 1929 roku. Na stadionie Panathinaikosu gospodarze przegrali wówczas z drugą reprezentacją Włoch 1:4.

Grecja zawsze uznawana była za piłkarskiego słabeusza - w latach 1954-90 eliminacje do kolejnych mistrzostw świata kończyła na ostatnim lub przedostatnim miejscu w grupie. W roku 1980 grała wprawdzie w mistrzostwach Europy (w kwalifikacjach wyprzedziła Węgry i Związek Radziecki), ale we Włoszech, mimo remisu z RFN w ostatnim spotkaniu, odpadła z turnieju już po fazie grupowej (zdobyła jeden punkt, bramki 1:4). Na kolejny awans do wielkiej imprezy Grecy musieli czekać czternaście lat - w 1994 roku zadebiutowali na Mundialu. Na światowym czempionacie zaprezentowali się jednak słabo. W trzech meczach stracili dziesięć bramek, nie strzelając ani jednej (0:4 z Argentyną, 0:4 z Bułgarią i 0:2 z Nigerią). Nie pomogły im liczne zmiany kadrowe (w każdym spotkaniu grała niemal zupełnie inna jedenastka, po dziewięćdziesiąt minut rozegrał każdy z trzech bramkarzy). Co ciekawe w obu tych turniejach reprezentację prowadził ten sam szkoleniowiec - Alketas Panagoulias.

Na Euro 2004 Grecja, mimo iż w eliminacjach zajęła w grupie pierwsze miejsce, wyprzedzając m.in. Hiszpanię i Ukrainę, nie jechała w roli faworyta. Na boiskach Portugalii podopieczni niemieckiego trenera Otto Rehhagela wznieśli się jednak na wyżyny swoich umiejętności i ku zdumieniu większości obserwatorów zdobyli mistrzostwo Europy. Żelazna dyscyplina taktyczna i skuteczna gra w defensywnie (bramkarz Antonios Nikopolidis oraz obrońcy Traianos Dellas i Yourkas Seitaridis zostali wybrani do najlepszej jedenastki turnieju) sprawiły, że, chociaż Grecy nie grali efektownie, potrafili zwyciężyć wyżej notowanych rywali - obrońców tytułu Francję, Czechy i dwukrotnie Portugalię.

W eliminacjach do Mundialu 2006 reprezentacja przegrała z Ukrainą oraz Turcją. Mistrzowie Europy w roku 2005 w niczym nie przypominali drużyny, która kilka miesięcy wcześniej zdobyła najważniejsze trofeum drużyn narodowych na Starym Kontynencie. Z kretesem polegli również w Pucharze Konfederacji (dwie porażki i remis, bramki 0:3), a na przełomie marca i września przez 540 minut nie potrafili strzelić bramki.