בהגרלת משחקי הפלייאוף על ההעפלה שובצה ישראל מול . אולם, על הישגה של ישראל העיבה הפרשה שכונתה בתקשורת "פרשת נערות הליווי". ערב המשחק הראשון, שנערך באצטדיון רמת גן ב-13 בנובמבר 1999, אירחו חלק משחקני הנבחרת נערות ליווי בחדרי המלון שלהם. השחקנים אמנם לא ביצעו עבירה פלילית, אך לאחר שהפרשה נחשפה על ידי העיתונאי אביב הברון מ"מעריב" (בסיוע יונתן הללי), נמתחה עליהם ביקורת נוקבת בטענה שהדבר איננו מוסרי היות שחלקם נשואים ומשום שהם השחקנים המייצגים את המדינה, וכן שהדבר הפריע להם להתרכז במשחק. במשחק עצמו הובסה ישראל בתוצאה 0–5, ובמשחק הגומלין שנערך בקופנהגן הפסידה 0–3. מאוחר יותר טען שאול אייזנברג בספר "סדום ועמורה 2" כי מי שאירח את נערות הליווי היה למעשה המאמן שלמה שרף. אברהם גרנט, לימים מאמן הנבחרת, טען כי היה זה חלק מדפוס התנהגות של שחקני הנבחרת. אחת מהתוצאות של הפרשה הייתה הקמת ועדה לניסוח קוד אתי לשחקני הנבחרת.
2000–2009.
ריצ'רד מולר נילסן ואברהם גרנט.
בעקבות הכשלונות להעפיל למונדיאל 1994 ולמונדיאל 1998, ובעיקר לאחר הנזק התדמיתי הכבד של פרשת נערות הליווי, פוטר שלמה שרף מאימון הנבחרת. ההתאחדות החליטה למנות את המאמן הדני ריצ'רד מולר נילסן, שנחשב כבעל סיכויים טובים להוביל את ישראל למונדיאל ראשון מזה 32 שנים כיוון שזכה עם ביורו 1992. הטורניר המשמעותי הראשון בו השתתפה הנבחרת היה מוקדמות מונדיאל 2002. ישראל החלה את הטורניר ב-3 בספטמבר 2000 בניצחון 2–0 על , והמשיכה עם הפסד חוץ 0–2 ל באצטדיון סנטיאגו ברנבאו. לאחר מכן גברה ישראל על במשחק ביתי, ספגה הפסד חוץ 1–2 ל, וגברה על 2–0 במשחק חוץ. המשחק הבא, מול ספרד, הסתיים בתיקו 1–1. בעקבות התיקו 0–0 מול בוסניה והרצגובינה בסרייבו דורגה ישראל במקום השלישי בבית, בפער של שתי נקודות מאוסטריה שבמקום השני. המשחק המכריע בין ישראל לאוסטריה נערך באצטדיון רמת גן ב-27 בספטמבר, והסתיים בתיקו 1–1 לאחר שער שוויון של אנדריאס הרצוג בתוספת הזמן של המשחק. נילסן החליט להתפטר מתפקידו בעקבות הכישלון להעפיל למונדיאל ובעקבות הפסדים אחדים במשחקי ידידות, שהכבד מביניהם היה 1–7 ל, במשחק ידידות שנערך בקייזרסלאוטרן ב-13 בפברואר 2002. התבוסה לגרמניה הייתה הגדולה ביותר בתולדות הנבחרת, וזהה לזו שנחלה הנבחרת מול במסגרת מוקדמות מונדיאל 1934.
בשנת 2002 הוחלף נילסן על ידי אברהם גרנט. גרנט שאף להנהיג שינויים משמעותיים בנבחרת, ולהפחית בהדרגה את הגיל הממוצע של שחקניה. עם זאת, בעקבות התוצאות הלא טובות במוקדמות יורו 2004 הוא נאלץ לחזור ולהסתמך על שחקנים מבוגרים יותר. אחת מהבעיות העיקריות של הנבחרת בטורניר זה הייתה שלילת זכות האירוח על ידי אופ"א, שחששה מהמצב הביטחוני בישראל בעקבות התגברות הטרור הפלסטיני. כתוצאה מכך ערכה ישראל שני משחקי בית באצטדיון רנצו ברברה בפאלרמו שבאיטליה, ושניים נוספים בעיר אנטליה שבטורקיה. הנבחרת פתחה את הטורניר בניצחון ותיקו חוץ מול וקפריסין בהתאמה, ולאחר מכן ערכה שני "משחקי בית" בפאלרמו, בהם הפסידה לאלופת אירופה וניצחה את קפריסין. הניצחון הזה היה האחרון של הנבחרת בטורניר, שהיה אחד מהחלשים שלה והסתיים כשלזכות הנבחרת היו 9 נקודות. שני המשחקים הבאים היו מול , והסתיימו בתיקו 0–0 "ביתי" באנטליה ובהפסד בסלובניה. הטורניר הסתיים בתיקו מול מלטה החלשה ובהפסד חוץ לצרפת.
למרות הכישלון להעפיל ליורו המשיך גרנט לאמן את הנבחרת גם בטורניר מוקדמות מונדיאל 2006, בו הוגרלה ישראל לבית 4 ביחד עם , , , פעם נוספת נגד ו. המשחק הראשון היה מול צרפת החזקה בחוץ, וישראל הצליחה להפתיע את הפרשנים ולסיים אותו בתיקו 0–0 שנחשב לתוצאה טובה. לאחר מכן ערכה ישראל ארבעה משחקי בית באצטדיון רמת גן ומשחק אחד בחוץ. היא החלה את סדרת המשחקים בניצחון על קפריסין, המשיכה בתיקו מול שווייץ, וב-17 בנובמבר ניצחה את קפריסין באצטדיון GSP שבניקוסיה, ובכך זכתה לראשונה לניצחון כפול על קפריסין במוקדמות המונדיאל. המשחק הבא היה מול אירלנד באצטדיון רמת גן, והסתיים בתיקו 1–1 בזכות שער שוויון בדקה ה-90 של המחליף עבאס סואן, שמנע הפסד ביתי ראשון במוקדמות המונדיאל מאז ההפסד לפינלנד במוקדמות מונדיאל 1994.
כעבור ארבעה ימים אירחה ישראל את צרפת, וסיימה עמה בתיקו 1–1. בנגינת ההמנונים שלפני תחילת המשחק נשמעו שריקות בוז מהקהל בזמן נגינת המנון צרפת, בעקבות התבטאויות אנטי-ישראליות של השוער פביאן בארטז שגררו ביקורת בינלאומית. לאחר המשחק מול צרפת סיימה ישראל בתיקו 2–2 מול אירלנד בדבלין ובתיקו 1–1 בבזל מול שווייץ. שני המשחקים שנותרו לישראל היו מול איי פארו החלשה, ושניהם הסתיימו בניצחון. אולם, כיוון שצרפת גברה על קפריסין במחזור המשחקים האחרון דורגה ישראל במקום השלישי בגלל הפרש שערים נחות בהשוואה לזה של שווייץ שבמקום השני.
תקופת דרור קשטן.
גרנט החליט לא לחדש את חוזהו בנבחרת. מחליפו היה דרור קשטן, אחד המאמנים המצליחים בתולדות הכדורגל הישראלי. ישראל שובצה לבית קשה במוקדמות יורו 2008 עם , , , , ו, והתחרתה עמן על ההעפלה לטורניר שנערך באוסטריה ובשווייץ. קביעת סדר המשחקים לוותה במחלוקות רבות, ורק ב-3 במרץ 2006 הצליחו נציגי התאחדויות הכדורגל להגיע להסכמה. נקודת המחלוקת העיקרית הייתה דרישתה של רוסיה לארח את ישראל בחורף, שנתקלה בהתנגדות נחרצת של ההתאחדות לכדורגל והסתיימה בפשרה שהמשחק ייערך באוקטובר 2006, ויהיה הראשון נגד אחת משלוש הנבחרות החזקות של הבית.
על אף שמלחמת לבנון השנייה נגמרה כ-4 שבועות לפני המשחק השני, מול באצטדיון רמת גן, החליטה אופ"א להעבירו לעיר ניימיכן שבהולנד. שבוע לאחר המשחק בוטלה ההחלטה, ושאר משחקי הבית של הנבחרת התקיימו בישראל. במשחק עצמו גברה הנבחרת על אנדורה בתוצאה 4–1. ב-7 באוקטובר שיחקה ישראל ברוסיה, וסיימה בתיקו 1–1. משחקה הראשון של הנבחרת על אדמת ישראל בטורניר היה מול קרואטיה, ובימים שלפניו נמכרו כל 40,000 הכרטיסים האפשריים. למול יציעי אצטדיון מלאים הפסידה ישראל בתוצאה 3–4. לאחר ההפסד סיימה ישראל בתיקו 1–1 מול במשחק ידידות, במהלכו עלה לשחק בן סהר בפעם הראשונה והיה לשחקן הצעיר ביותר בתולדות הנבחרת. שיא זה נשבר מאוחר יותר על ידי גיא אסולין. ב-24 במרץ 2007 נערך המשחק הרשמי הראשון אי פעם מול אנגליה, שהסתיים בתיקו 0–0. ארבעה ימים לאחר מכן אירחה ישראל את אסטוניה וניצחה אותה 4–0.
שני המשחקים הבאים של הנבחרת היו משחקי חוץ. ב-2 ביוני גברה ישראל על מקדוניה בתוצאה 2–1 בסקופיה, וארבעה ימים לאחר מכן ניצחה את אנדורה 2–0 למרות תנאי המגרש הגרועים. לפני המשחק מול אנגליה באצטדיון ומבלי הפגינה הנבחרת יכולת חלשה, ששיאה היה בהפסד 1–2 לבלארוס במשחק ידידות. במשחק מול אנגליה ב-8 בספטמבר הפסידה ישראל 0–3, ולא הצליחה לבעוט לכיוון השער ולו פעם אחת. במשחק מול קרואטיה ב-13 באוקטובר הפגינה ישראל רמת משחק יותר גבוהה, מה שלא מנע ממנה להפסיד 0–1. ב-17 בנובמבר גברה ישראל על רוסיה 2–1 באצטדיון רמת גן, שהיה ניצחונה הראשון במשחק רשמי מאז יוני 1999 על נבחרת המדורגת מעליה בדירוג פיפ"א. ב-21 בנובמבר ניצחה ישראל את מקדוניה 1–0 במשחק ביתי, ובעקבות כך סיימה את הטורניר במקום הרביעי, בפער של נקודה מרוסיה שסיימה במקום השני והעפילה ליורו 2008. בזכות הישגיה בטורניר העפילה ישראל למקום ה-27 בדירוג פיפ"א, וזכתה להגרלה נוחה יותר במוקדמות מונדיאל 2010.
הגרלת משחקי המוקדמות של מונדיאל 2010 נערכה ב-25 בנובמבר 2007 בעיר דרבן שבדרום אפריקה, מארחת המונדיאל. ימים אחדים לפני ההגרלה גברה ישראל כאמור על ועל , ובזכות כך דורגה בקבוצת האיכות השנייה. בהגרלה שובצה ישראל לבית מספר 2 ביחד עם (אלופת אירופה בשנת 2004), , , ו. גם הפעם היו מחלוקות בקרב התאחדויות הכדורגל על לוח המשחקים, ובסופו של דבר התערבה פיפ"א וב-30 בינואר 2008 ערכה הגרלה לקביעת סדר המשחקים. ישראל פתחה את הטורניר בתיקו 2–2 ביתי מול שווייץ, ולאחר מכן יצאה לסדרה של שלושה משחקי חוץ, בהם זכתה לניצחונות על מולדובה באצטדיון זימברו ועל לוקסמבורג באצטדיון העירוני של לוקסמבורג סיטי וסיימה בתיקו 1–1 מול לטביה. סיבוב המשחקים השני התנהל במתכונת הפוכה לסדר המשחקים של הסיבוב הראשון. ארבעה ימים לאחר המשחק מול יוון ברמת גן, שהסתיים בתוצאה 1–1, ספגה הנבחרת הפסד 1–2 בהרקליון, וכתוצאה מכך הייתה זקוקה לניצחון במשחק הביתי מול לטביה ברמת גן ב-5 בספטמבר. עם זאת, ישראל הפסידה 0–1, וספגה הפסד ביתי ראשון במוקדמות המונדיאל מזה 15 שנים. ארבעה ימים לאחר ההפסד הביסה ישראל 7–0 את לוקסמבורג, וב-10 באוקטובר גברה 3–1 על מולדובה ברמת גן. ניצחון זה הותיר לישראל סיכוי להעפיל לפלייאוף היבשתי מהמקום השני, אך ב-14 באוקטובר שיחקה ישראל מול שווייץ בזנקט יאקוב פארק, וסיימה בתיקו ללא שערים, בעקבותיו דורגה במקום הרביעי כיוון שלטביה גברה על מולדובה.
2010–2020.
תקופת לואיס פרננדס.
בעקבות רצף הכישלונות של דרור קשטן החליט אבי לוזון, יושב ראש ההתאחדות לכדורגל, כי חוזהו של קשטן כמאמן הנבחרת לא יוארך. בעקבות האכזבה מהישגיהם של המאמנים הישראלים נטתה הכף לטובת העסקתו של מאמן זר בעל הישגים, ולאחר בחינת מספר מועמדים הוחלט למנות את הצרפתי לואיס פרננדס, שהיה חסר ניסיון באימון נבחרות כדורגל.