בבחירות לראשות הממשלה התמודדו נגד נתניהו אהוד ברק, מועמד מפלגת העבודה; יצחק מרדכי, שאותו פיטר נתניהו מתפקיד שר הביטחון, כשגילה כי הוא מתכוון להצטרף למפלגת המרכז ולרוץ נגדו; בני בגין, שעזב את הליכוד והועמד בראש האיחוד הלאומי, ועזמי בשארה. בסופו של דבר פרשו מרדכי, בגין ובשארה מהמרוץ, בגין תמך במועמדותו של נתניהו, ואילו מרדכי ובשארה תמכו במועמדותו של ברק, שניצח בסופו של דבר במאי 1999, כשזכה ברוב של 56% מקולות הבוחרים.
נתניהו הודה בתבוסתו עוד לפני פרסום התוצאות הסופיות, והודיע על נטילת פסק זמן מהפוליטיקה, כשלצידו עומד אריאל שרון, שהוצג כמחליפו בראש הליכוד. לימים תלה נתניהו את כישלונו בקדנציה הראשונה, בכך שלא הקים ממשלת אחדות עם בחירתו, ושלא שיער עד כמה עמוקים הקרע בעם והטינה שרחש לו השמאל.
הפרישה מהפוליטיקה והחזרה (1999–2003).
לאחר שהפסיד בבחירות 1999, פרש נתניהו מהנהגת הליכוד ומחברותו בכנסת, ובאוגוסט 1999 מונה ליועץ לחברת באטמ תקשורת מתקדמת ולחברת "אלקטריק פיול".
עם נפילת ממשלת ברק בסוף שנת 2000, ביטא נתניהו שאיפה לחזור לפוליטיקה. על פי חוק, התפטרות ברק אמורה הייתה להוביל לבחירות לראשות הממשלה בלבד. נתניהו דרש שיתקיימו גם בחירות לכנסת, בנימוק שאחרת לא תתאפשר הקמת ממשלה יציבה. ש"ס, שלא רצתה להסתכן בירידת כוחה, סירבה לתמוך בפיזור הכנסת, אך סייעה להעברת חוק שאיפשר לנתניהו להתמודד בבחירות המיוחדות לראשות הממשלה. נתניהו החליט שלא להתמודד, החלטה שהובילה לעלייתו המפתיעה לשלטון של אריאל שרון, שנחשב באותה עת ל"בלתי בחיר" ולפופולרי פחות מנתניהו.
בטרם מבצע "חומת מגן", תקף נתניהו את הבלגתו של שרון מול הפיגועים וקרא לכניסת צה"ל לערים הפלסטיניות. הוא קרא גם ליצירת הפרדה בין השטחים הפלסטיניים לישראל, אם כי שמר על עמימות לגבי האופן שבו תבוצע הפרדה זאת. רק מאוחר יותר היה מתומכיה של גדר ההפרדה. עם פירוק ממשלת האחדות בסוף שנת 2002, הצטרף נתניהו לממשלת שרון כשר החוץ. הוא התמודד מול שרון על הנהגת הליכוד, אך הפסיד בבחירות הפנימיות בנובמבר בהפרש של 24%.
קדנציה כשר אוצר (2003–2005).
שר האוצר.
עם כינון ממשלת שרון השנייה בתחילת 2003, הוצע לנתניהו תפקיד שר האוצר. נתניהו, שחפץ בתיק החוץ, סירב תחילה, אך לבסוף קיבל את התפקיד, לאחר שהובטחה לו יד חופשית וגיבוי מצד ראש הממשלה, הבטחה שאכן קוימה במהלך הקדנציה. נתניהו גרס כי עידוד כלכלת השוק יביא לצמיחה ולשיפור המצב הכלכלי במשק. במהלך כשנתיים וחצי שבהן כיהן כשר אוצר, ערך רפורמות מרחיקות לכת בתחומים שונים, בעיקר בתחום המיסוי ושוק ההון. הוא הוביל מדיניות קפיטליסטית תקיפה, וקידם יוזמות להפחתת הוצאות הממשלה, קיצוצים נרחבים בתקציבי הרווחה והפרטת חברות ממשלתיות.
צעדים בולטים של נתניהו כשר האוצר:
גרעין השליטה בבנק דיסקונט נמכר לקבוצת משקיעים בראשות מתיו ברונפמן, תמורת 1.3 מיליארד ש"ח, כ-80% משווי השוק, על פי מחיר המניות שנסחרו באותה העת בבורסה. חברת התקשורת "בזק" נמכרה לקבוצה בראשות חיים סבן ואייפקס, במחיר הקרוב לשוויה הבורסאי. נתניהו המשיך בניסיונות קודמיו ומחליפיו בתפקיד למכור את גרעין השליטה בבנק לאומי, אך גם בשנת 2008 לא היה הבנק בידיים פרטיות.
בתקופת כהונתו השתפרו באופן משמעותי המדדים הכלכליים של המשק בישראל:
בסוף 2002 התקשתה מדינת ישראל לגייס כסף במדינות זרות, מאחר שהחוב הממשלתי גדל באופן ניכר. בדו"ח היציבות הפיננסית של בנק ישראל לשנת 2003 צוין, כי שיפור מעמדה של ישראל בשווקים הפיננסיים נבע, בין השאר, מהקמת ממשלה חדשה, יציבה ובעלת תוכנית כלכלית, ומהקיצוצים בתקציב (אף שעוד לא באו לידי ביטוי בגירעון של אותה שנה), זאת בנוסף לגורמים כמו השיפור במצב השווקים בעולם, קבלת הערבויות האמריקאיות והשיפור במצב הביטחוני.
בשנת 2007 פרסמה מחלקת המחקר של בנק ישראל מאמר שבו נאמר כי מדיניותה המקרו-כלכלית של הממשלה בתקופתם של נתניהו, של אהוד אולמרט ושל אברהם הירשזון שהחליפו, גרמה לשליש מהצמיחה במשק, ואילו גורמים חיצוניים, כמו השיפור במצב הביטחוני וצמיחת הסחר העולמי גרמו לשני שלישים מהצמיחה.
נתניהו ספג ביקורת מהארגונים החברתיים, בשל עלייה גדולה בשיעור העוני וגידול משמעותי במדד האי-שוויון במשק. על-פי דוחות של המוסד לביטוח לאומי, שיעור העוני בין 2002 ל-2004 עלה בכ-10%, ומספר הילדים החיים במשפחות עניות עלה ל-12%. ארגוני רווחה דיווחו על עלייה בדרישת הנזקקים למזון ולתרופות, גם בקרב אזרחים שהשתייכו בעבר למעמד הביניים, בקרב אזרחים עובדים או פנסיונרים. העוני התרחב בעיקר כתוצאה מהקיצוצים בתשלומי הרווחה והקצבאות.
יחסו לתוכנית ההתנתקות.
נתניהו הסתייג מתוכנית ההתנתקות ובפרט לנסיגה מציר פילדלפי, בנימוק שנסיגה משם תביא להברחת אמצעי לחימה לרצועה בהיקף גדול. בנוסף, הוא צידד בעריכת משאל עם בנושא. כשעלתה התוכנית בכנסת, הצביע נתניהו בעדה במסגרת המשמעת הקואליציונית, אך הציב אולטימטום לראש הממשלה שלפיו יתפטר אם לא יבוצע משאל עם. בהמשך נסוג בו מהאולטימטום, באומרו שהחרפת מצבו הרפואי של יאסר ערפאת, שאירעה בינתיים, דורשת בדיקה מחדש של המצב. בהמשך שב ותבע קיומו של משאל עם. עם זאת הצביע נתניהו יחד עם הממשלה בעד התוכנית בהצבעות שנערכו בנושא בכנסת. ב-7 באוגוסט 2005, ערב ביצוע הפינוי, במהלך ישיבת ממשלה שבה הוחלט על פינוי שלושת היישובים הראשונים, הודיע נתניהו על התפטרותו. הוא נימק את החלטתו להתפטר בחששו שבעזה צפוי לקום "בסיס טרור שיסכן את ביטחון ישראל" ובאומרו ש"רפורמת בכר" בבנקים השלימה את הרפורמות שביקש לערוך במסגרת תפקידו. תומכי אריאל שרון טענו שעיתוי ההתפטרות והקישור שלה להתנתקות פוליטיים ואינם ענייניים.
בראשות האופוזיציה (2009-2005).
ב-30 באוגוסט 2005 הודיע נתניהו על התמודדותו לראשות הליכוד ולראשות הממשלה מול אריאל שרון. אחדים מחברי הכנסת של הליכוד הצהירו על תמיכתם בנתניהו. ימים ספורים לאחר מכן הכריז גם חבר הכנסת עוזי לנדאו על מועמדותו לתפקיד.
נתניהו החל לתקוף את אריאל שרון, וטען כי הוא מוביל את הליכוד בדרך שהיא "שמאלה ממרצ". יחד עם לנדאו ונציגי מרכז הליכוד שהתנגדו לדרכו של שרון, פעל נתניהו להקדמת הבחירות המקדימות לבחירת יו"ר הליכוד, במטרה להדיח את שרון מתפקיד יושב ראש המפלגה, אך ההצעה נדחתה על ידי מרכז הליכוד (ספטמבר 2005) בהפרש קולות קטן. למרות הפסדו, הצהיר נתניהו כי ימשיך להתמודד על תפקיד יושב ראש התנועה.
בראשות הליכוד.
בתחילת דצמבר 2005, בעקבות פרישתו של אריאל שרון למפלגה עצמאית בשם "קדימה", הפך נתניהו למועמד המוביל להנהגת הליכוד בבחירות לכנסת השבע עשרה. מולו התמודדו בפריימריז סילבן שלום, ישראל כץ ומשה פייגלין. עוזי לנדאו, שהתמודד בתחילה, הסיר את מועמדותו והודיע על תמיכה בנתניהו, ואילו שאול מופז, שהתמודד בתחילה גם הוא, עבר למפלגת "קדימה". בבחירות הפנימיות שנערכו ב-19 בדצמבר 2005 נבחר נתניהו לראשות הליכוד בקולות 44% מן המצביעים (מול 33% לשלום, 12% לפייגלין ו-9% לכץ).
ב-2 במרץ 2006 הצליח לאשר במרכז הליכוד החלטה המעבירה את בחירות הרשימה לכנסת לפריימריז פתוחים בין כל חברי התנועה, ובכך ניטל למעשה כוחו הפוליטי של מרכז התנועה, שנחשב (לפי סקרים שונים) כשנוא בציבור וכמקור לשחיתות בתנועה. התגובות לצעד זה בעיתונות היו מעורבות, מחד זכה לתשבחות על שנלחם למען טוהר המידות במפלגה ועל שהצליח לגרום למרכז לוותר מרצון על עוצמתו, משימה שנראתה עד אז כבלתי אפשרית; מאידך היו שטענו כי מדובר בתיקון קוסמטי בלבד, בהצביעם על העובדה כי הצעד ננקט לאחר שכבר נבחרה רשימת הליכוד לכנסת ה-17, וכי ניתן יהיה להחזיר את המצב לקדמותו לאחר הבחירות.
הבחירות לכנסת ה-17 הביאו עמן מפלה לליכוד בראשות נתניהו, שזכה ב-12 מנדטים, זאת אף על פי שהמועמד שכנגד היה אהוד אולמרט ולא אריאל שרון, ועל אף עליית חמאס ברשות הפלסטינית ונטילת כוחם של חברי המרכז, שנראו כולם כעומדים לחזק את המפלגה. בנאום התבוסה, קשר נתניהו בין מדיניותו הכלכלית, שפגעה בשכבות החלשות, לבין הכישלון בבחירות, אך קבע כי זו הייתה הכרחית למען הצלת המדינה והודיע שימשיך לעמוד בראש התנועה. בכנסת ה-17 כיהן נתניהו כראש האופוזיציה. בנאומים שנשא כראש האופוזיציה ובעקבות מלחמת לבנון השנייה הדגיש את הסכנה הנשקפת מאיראן המתחמשת בפצצת אטום והשווה אותה לגרמניה הנאצית. בשנת 2008 אישרה הכנסת הצעת חוק פרטית של נתניהו שעסקה באיסור השקעה בתאגידים המקיימים קשר עם איראן.
הבחירות לכנסת השמונה עשרה.
ב-14 באוגוסט 2007 נערכו בחירות לראשות הליכוד. יריבו העיקרי של נתניהו במפלגה, סילבן שלום, פרש בהפגנתיות מהמרוץ לראשות המפלגה בשל הקדמת הפריימריז, תוך שהוא משאיר את נתניהו כמועמד עיקרי יחיד מול פעילים עם כוח מועט במפלגה, משה פייגלין ודני דנון. נתניהו זכה ברוב של 72.8%, וביסס את מעמדו כמנהיג הליכוד וכמועמד המפלגה לראשות הממשלה בבחירות הבאות. מאוחר יותר פעל נתניהו, באמצעות מקורבו, אופיר אקוניס, לדחיקתו של פייגלין אחורה ברשימת המועמדים למקום ה-36, לאחר שזה נבחר למקום ה-20.
ממשלת אולמרט נחלשה לאחר מלחמת לבנון השנייה שנתפסה ככישלון בציבור. אולמרט נחשד בפלילים והחלו בקיעים בקואליציה שבסופם התפטר. מחליפתו, ציפי ליבני, כשלה בהקמת ממשלה ופוזרה הכנסת.
אחד מהנושאים המרכזיים במערכת הבחירות היה ירי הקסאמים מרצועת עזה על ידי החמאס ובמהלכה היה מבצע עופרת יצוקה. נתניהו הביעו את עמדתו ביחס לשלטון החמאס ברצועה ותמך בהמשך המבצע. הקמפיין עצמו כלל ביקורת כלפי לבני וסיסמאות כמו "חזק בביטחון, חזק בכלכלה".