המשחק הראשון במוקדמות נערך מול יוון באתונה ב-1 בנובמבר 1953, והסתיים בהפסד 0–1 בלבד בזכות יכולת טובה של השוער חודורוב. כעבור שבוע, ב-8 בנובמבר, שיחקה ישראל מול יוגוסלביה בבלגרד והפסידה פעם נוספת בתוצאה 0–1. ישראל שיחקה היטב במשחק זה, אך חודורוב נכנע לבעיטה של מילוטינוביץ' היוגוסלבי בגלל תנאי המגרש הגרועים ומאחר שנעל נעלי גומי שלא התאימו לדשא החלקלק. בדקה ה-80 נפגע חודורוב בכתפו וספג פציעה, אך למרות הכאבים העזים סירב להתחלף. לקראת הגומלין מול יוון ב-7 במרץ ברמת גן היו ציפיות גבוהות מהנבחרת לאור השעייתם של כל שחקני הסגל היריב למעט המגן אליאס רוסידיס, אך המשחק הסתיים בהפסד 0–2 והוגדר על ידי העיתונות ככישלון ספורטיבי. בעקבות כך נערכו שינויים אחדים בהרכב הנבחרת, בראשם הדחתו מהסגל של הקפטן אלי פוקס, ושבועיים לאחר מכן, ב-21 במרץ, הפסידה ישראל ליוגוסלביה ברמת גן בתוצאה 0–1. שני המשחקים בין יוון ליוגוסלביה הסתיימו בתוצאה 1–0 לטובת יוגוסלביה, שהעפילה למונדיאל מהמקום הראשון ללא הפסד ועם הפרש שערים של 4–0.
בין ההפסד הביתי ליוון להפסד הביתי ליוגוסלביה יצאה הנבחרת למסע משחקים בדרום אפריקה למטרות גיבוש. ישראל התמודדה מול קבוצות מקומיות אחדות, ובמשחק המרכזי הפסידה לנבחרת המקומית בתוצאה 1 –2. בסיום הטורניר, שהחל ב-29 במרץ והסתיים באמצע מאי, עמד מאזנה של הנבחרת על 6 ניצחונות, 3 תוצאות תיקו ו-2 הפסדים, והפרש שערים של 28–12.
תחילת הדרך האולימפית ומוקדמות המונדיאל שכמעט ולא היו.
לקראת אולימפיאדת מלבורן ב-1956 הוגרלה ישראל לצמד משחקים מול החזקה, בשורותיה שיחק לב יאשין, הנחשב לאחד מגדולי השוערים בתולדות הכדורגל. לפני המשחק פורסמה דרישה מצד משרד ראש הממשלה ולפיה כל שחקני הנבחרת מחויבים לעברת את שמם, אחרת לא יוכלו להשתתף במשחקים. ב-4 ביולי המריאה המשלחת הישראלית לבריסל בדרכה למוסקבה, אך חלק מחבריה נאלצו להמתין לטיסה נוספת בגלל מחסור במקומות במטוס האיליושין בו טסה הנבחרת למוסקבה. במשחק עצמו, שנערך לעיני קהל שמנה בין היתר אלפי יהודים סובייטיים, הפסידה ישראל 0–5. גם הפעם הצטיין השוער חודורוב ומנע הפסד כבד יותר. הציפיות לקראת משחק הגומלין ברמת גן ב-31 ביולי היו נמוכות. למרות זאת הפגינה ישראל יכולת גבוהה בהגנה, וספגה שער רק בדקה ה-57. לאחר מכן הובקע אחד השערים הידועים ביותר בתולדות הנבחרת. בועז קופמן מהפועל פתח תקווה רץ לאורך המגרש, הגביה את הכדור לעבר רחבת העונשין, ושם התרומם חברו לקבוצה נחום סטלמך והכניע את יאשין. היה זה שער הבכורה של סטלמך בנבחרת במשחקו השני בשורותיה, כאשר את הופעת הבכורה שלו ערך במשחק הקודם מול ברית המועצות. אחד הרגעים הזכורים לאחר הבקעת השער היה כאשר השדרן נחמיה בן אברהם קרא את קריאתו הנרגשת
המשחק עצמו הסתיים בהפסד של ישראל לאחר שער ניצחון של בוריס טאושין בדקה ה-79.
במוקדמות מונדיאל 1958 הודרכה ישראל על ידי המאמן האנגלי ג'ק גיבונס, והייתה אמורה לשחק בשלושה סבבים על מנת להעפיל למונדיאל בשוודיה. בסיבוב המוקדמות הראשון הוגרלה ישראל לבית מספר 2 האפריקני-אסייתי מול טורקיה, והעפילה אוטומטית לסיבוב השני בגלל סירובה של טורקיה לשחק מולה בפרט, ועל אדמת ישראל בכלל. בשלב השני הייתה אמורה ישראל לשחק מול , אך זו פרשה לאחר שפיפ"א דחתה את בקשתה לשחק מול ישראל במגרש נייטרלי. מצרים פרשה גם כן, כך ש, הנבחרת הרביעית בבית, העפילה אוטומטית ביחד עם ישראל לסיבוב הבא. גם סודאן סירבה לשחק מול ישראל, בשלב השלישי, ולפיכך הייתה אמורה הנבחרת להעפיל אוטומטית למונדיאל.
עם זאת, פיפ"א קבעה כי למעט האלופה המכהנת כל נבחרת חייבת לשחק לפחות פעם אחת על מנת להעפיל למונדיאל, והחליטה שישראל תשחק מול אחת מסגניות בתי המוקדמות של אופ"א (התאחדות הכדורגל של אירופה). ב-15 בדצמבר נערכה הגרלה במשרדי פיפ"א בעיר ציריך שבשווייץ, ובה עלה שמה של , בשורותיה שיחק החלוץ הידוע ג'ון צ'ארלס. לקראת המשחקים מונה משה וארון לתפקיד המאמן. המשחק הראשון, שנערך ברמת גן ב-15 בינואר 1958, הסתיים בהפסד 0–2. גם המשחק השני, שנערך בקארדיף שבוויילס ב-5 בפברואר, הסתיים באותה תוצאה. למרות כישלונה של הנבחרת להעפיל למונדיאל, היא זכתה למחמאות מהתקשורת הישראלית בזכות מאמציה מול ויילס, שנחשבה באותה עת לאחת הנבחרות הטובות בעולם. המשחק בוויילס נחשב לאחד הזכורים ביותר בקריירה של השוער יעקב חודורוב, שהמשיך לשחק גם לאחר ששבר את אפו ונקע את כתפו. ויילס העפילה עד רבע גמר המונדיאל.
ארבעה חודשים לאחר הכישלון להעפיל למונדיאל נערך הטורניר השלישי של המשחקים האסיאתיים. רוב חברי המשלחת היו שחקני נבחרת הכדורגל. בעקבות ניצחונות על איראן (4–0) וסינגפור (2–1) העפילה ישראל לרבע הגמר, בו הודחה לאחר הפסד 0–2 ל. ישראל סיימה את הטורניר במקום החמישי בזכות הפרש שערים שהשיגה במשחקיה. בעקבות כישלון זה הוקמה ועדת חקירה בשם "ועדת טוקיו", שהשעתה את פעילות הנבחרות למשך שנה. תוצאות נוספות של הכישלון היו התפטרותם של המאמן משה וארון ומרכיב הנבחרת אלוף-משנה שמואל סוחר, והשעייתם בגין בעיות משמעת של נחום סטלמך, יוסף גולדשטיין, בועז קופמן ושלמה נהרי.
ב-11 ביוני 1959 מונה למאמן היהודי-הונגרי גיולה מאנדי, שהתפרסם בזכות הדרכת נבחרת הונגריה במונדיאל 1954. במשחק הראשון תחת הדרכתו הפסידה ישראל לקבוצת אמריקה הברזילאית בתוצאה 0–1, ובהמשך הובסה הנבחרת על ידי בתוצאה 2–7. מאנדי הנהיג חידוש בכדורגל הישראלי באותה עת בכך שבעצה אחת עם בכירי המאמנים בארץ הרכיב סגל רחב של 60 שחקנים, ממנו ברר את הסגל הסופי של הנבחרת. משחקה הרשמי הראשון של ישראל בהדרכת מאנדי היה באצטדיון רמת גן מול יוגוסלביה במסגרת מוקדמות אולימפיאדת רומא, והסתיים בתיקו 2 - 2 בזכות יכולת גבוהה של כל השחקנים. לימים נודע משחק זה כראשון אי פעם שבו הושמעה הקריאה "אל אל ישראל". עד למשחק זה עודד הקהל את הנבחרת בקריאות "שייע, שייע, שייע!" על שם החלוץ שייע גלזר. חודש לפני המשחק ערך העיתון "חדשות הספורט" תחרות לבחירת סיסמת עידוד חדשה לנבחרת. ועדה שחבריה היו יו"ר ההתאחדות לכדורגל יצחק זאבי, העיתונאי יהודה גבאי והמשורר חיים חפר בדקה 177 הצעות מרחבי הארץ, ובחרה את ההצעה הזוכה שהושמעה פעמיים בתחילת המחצית השנייה ופעם נוספת על ידי כל הקהל לאחר שער השוויון של אברהם מנצ'ל.
לאחר תחילת מוקדמות הטורניר האולימפי נסעה הנבחרת הישראלית להשתתף בטורניר המוקדמות של גביע אסיה בכדורגל. קונפדרציית הכדורגל של אסיה קבעה כי טורניר זה ייערך בהודו, ובגלל תנאי החום הקשים הוחלט שכל משחק יימשך 80 דקות בלבד. בגלל הכנה לקויה הפסידה ישראל ל במשחק הפתיחה בתוצאה 0–3, אך התאוששה וניצחה את ואת . בעקבות התיקו מול איראן והניצחון הנוסף על הודו, ישראל הייתה זקוקה לנקודה כדי להעפיל לטורניר הגמר, והשיגה אותה בזכות תיקו 2–2 מול פקיסטן. לאחר טורניר זה התחדשו משחקי מוקדמות האולימפיאדה. במשחק הבית מול יוון ניצחה ישראל 2–1, ובגומלין הפסידה בתוצאה זהה. ב-10 באפריל הפתיעה ישראל את יוגוסלביה בבלגרד, גברה עליה 2–1 והעפילה למקום הראשון בבית המוקדמות. עם זאת, בעקבות הניצחון היוגוסלבי על יוון במחזור האחרון סיימה ישראל במקום השני עם הפרש שערים פחות טוב מזה של יוגוסלביה, שהמשיכה עד לזכייה במדליית הזהב באולימפיאדה.
בעקבות הניצחון על יוגוסלביה וטורניר המוקדמות כולו, שעוררו גל של גאווה לאומית בישראל, כתב הסופר שרגא גפני את ספר הילדים "בעט אלון בעט", שדמויות גיבוריו התבססו על השוער יעקב חודורוב ועל החלוץ המרכזי רפי לוי. הספר הפך במהירות לרב-מכר ובעקבות הספר הראשון יצאו ספרי המשך נוספים, שגם הם זכו להצלחה מסחרית, והפכו לסדרה בשם "הספורטאים הצעירים".
שנות ה-60: העפלה למונדיאל ראשון.
שלושה מאמנים בחמש שנים.
ישראל החלה את שנות ה-60 של המאה ה-20 בהשתתפות בגביע אסיה 1960, אליו העפילה בסיום העשור הקודם. מאנדי ערך אימונים רבים לפני תחילת הטורניר בסיאול, בירת קוריאה הדרומית. הטיסה למזרח אסיה הייתה מתישה עבור השחקנים, ותוך זמן קצר מהנחיתה, ב-17 באוקטובר 1960, התמודדה ישראל מול הנבחרת המארחת, שזכתה בטורניר הקודם של גביע אסיה. הקוריאנים היו עדיפים על ישראל, ותוך 13 דקות במחצית הראשונה הבקיעו שני שערים, וסיימו את המשחק בניצחון 0–3. ישראל הצליחה להתאושש מהתבוסה לקוריאנים ולנצח את (5–1) ואת טיוואן (1–0). ישראל הפגינה יכולת גבוהה מאוד במשחקים אלה, ובזכות כך נכללו ארבעה משחקניה (מרדכי בנבנישתי, אמציה לבקוביץ', אהרון אמר ונחום סטלמך) בנבחרת הטורניר.