כראש האופוזיציה וכמנהיג הימין, ביקר נתניהו בחריפות את הסכמי אוסלו מ-1993, והזהיר שההסכם יביא לגל טרור כלפי אזרחי מדינת ישראל. נתניהו ביקר באתרים של פיגועי טרור (כגון באתר הפיגוע בקו 5 ב-19 באוקטובר 1994), והשתתף בהפגנות של הימין, קטנות וגדולות, כנגד מדיניות ממשלת רבין. בין הבולטות בהפגנות אלה הייתה הפגנת הימין בכיכר ציון נגד יצחק רבין והסכם אוסלו ב', שנערכה באוקטובר 1995. השתתפותו בהפגנה בצומת רעננה, שבה נישא ארון קבורה עליו הכיתוב "רבין קובר את הציונות", והוצג בה חבל תלייה - זכתה לפרסום רב. נתניהו אמר שלא ראה את הארון.
הניצחון בבחירות 1996.
ב-29 במאי 1996 נערכו הבחירות לכנסת הארבע-עשרה, לפי שיטת הבחירה הישירה. בהתמודדות על תפקיד ראש הממשלה גבר נתניהו על ראש הממשלה המכהן, שמעון פרס (שהחליף את רבין לאחר הירצחו), ברוב של 50.5% לעומת 49.5% לפרס, ובהפרש של כ-29,000 קולות. ניצחונו התקבל בהפתעה על ידי הפרשנים הפוליטיים, לאחר שרוב הסקרים ניבאו ניצחון לפרס, חלקם בהפרש של יותר מחמישה אחוזים. גם במדגם הטלוויזיה של הערוץ הראשון ניצח פרס את נתניהו בהפרש של 1.4%, וכך גם במניין החלקי של תוצאות האמת במהלך הלילה. לפנות בוקר, התהפכו התוצאות לטובת נתניהו. ניצחון נתניהו בבחירות הפך אותו בגיל 47 לראש הממשלה הצעיר ביותר שנבחר בישראל, ולראשון שנולד בישראל לאחר קום המדינה.
פרשנים מציינים כמה גורמים שתרמו לניצחון נתניהו:
קדנציה ראשונה כראש הממשלה (1996–1999).
נתניהו כיהן לראשונה כראש ממשלת ישראל מ־18 ביוני 1996 עד ל־6 ביולי 1999.
התחום המדיני.
הנושא המרכזי שהעסיק את נתניהו בתקופת כהונתו הראשונה כראש ממשלה היה היחסים בין ישראל לפלסטינים, שידעו עליות ומורדות. כפי שהתחייב נתניהו מראש, הוא לא ביטל את הסכמי אוסלו. עם זאת, הוא אמר שיש לדאוג להדדיות ולקיים התחייבויות לנסיגות רק במקביל לקיום הרשות הפלסטינית את התחייבויותיה. בהתאם לכך, המשיך את ההתמהמהות של קודמו שמעון פרס בביצוע מסירת חברון לידי הרשות, העיר היחידה שלא נמסרה לפלסטינים בהתאם להסכמי אוסלו ב', לשליטה פלסטינית. בתחילת ספטמבר 1996 נפגש נתניהו עם יאסר ערפאת במעבר ארז, אולם לא הושגו בפגישה הסכמות.
ב-24 בספטמבר 1996 החליט נתניהו על פתיחת מנהרות הכותל בירושלים; בעקבות זאת פרצו מהומות מנהרת הכותל בכל רחבי יהודה ושומרון ובצפון רצועת עזה, ובמהלכן נהרגו 17 חיילי צה"ל וכמאה שוטרים ואזרחים פלסטינים. לטענת הפלסטינים, המהומות התפתחו בעקבות פתיחת הפתח הצפוני של מנהרת הכותל בוויה דולורוזה שבמרכז הרובע המוסלמי בירושלים, בתואנה שישראל חופרת תחת מסגדי הר הבית במטרה לערער אותם. נתניהו הצדיק את האישור שנתן לפתיחת פתח המנהרה בהתאם לחוות דעת של מערכת הביטחון, ואמר שהיא מאפשרת "נגיעה בסלע קיומנו". מדובר היה באירוע ביטחוני משמעותי בתקופת כהונתו של נתניהו, הן בשל מספר ההרוגים הגבוה בצד הישראלי והפלסטיני והן בשל המחאות החריפות של ערביי ישראל, כולל שביתה כללית והפרות סדר בערים הערביות ובערים המעורבות, שנפסקו תוך ימים ספורים.
בעקבות מהומות מנהרת הכותל מיהר נשיא ארצות הברית ביל קלינטון לקרוא לנתניהו ולערפאת לפסגה בוושינגטון, בהשתתפות חוסיין מלך ירדן. הפסגה סללה את הדרך לחתימת "הסכם חברון" בינואר 1997. בהסכם התחייבה ממשלת נתניהו לסגת מרוב שטחה של העיר חברון, למעט אזור מערת המכפלה ואזורים סמוכים שבהם קיימים בתים המאוכלסים בישראלים. כמו כן התחייבה ישראל לקיים שתי נסיגות נוספות שביחד עם הנסיגה מחברון נקראו "שלוש הפעימות". הנסיגה מחברון בוצעה באותו חודש.
בקיץ 1997 התרחשו בירושלים שני פיגועי התאבדות, ובעקבותיהם הורה נתניהו על הריגתו, באמצעות רעל, של ראש הלשכה המדינית של חמאס בירדן, חאלד משעל (ראו ניסיון ההתנקשות בח'אלד משעל). הפעולה לא עלתה יפה, וסוכני "המוסד" שביצעו אותה נתפסו. בתמורה לשחרורם שלחה ישראל תרופת נגד שהצילה את חייו של משעל, ושחררה עשרות אסירים פלסטינים, בראשם שייח' אחמד יאסין. קודם לכן החליט נתניהו שלא לדרוש את הסגרתו של מוסא אבו מרזוק, בכיר חמאס שנתפס בארצות הברית, מחשש שמשפטו יעורר את הארגון לחדש את הפיגועים.
לאחר תקופה ארוכה של קיפאון, שבמהלכה דרשו הפלסטינים כי נתניהו יקיים את ההתחייבויות שניתנו בהסכמי אוסלו ובהסכם חברון לנסיגות נוספות, כינס הנשיא קלינטון את ועידת ואי באוקטובר 1998. בוועידה הסכים נתניהו, מלווה באריאל שרון, שהתמנה לשר החוץ שלו במקום דוד לוי שהתפטר, לנסיגה נוספת, שכללה 13% משטחי C שבגדה שהועברו לשטחי A ו-B, 1% ו-12% בהתאמה, ולפתיחת נמל תעופה בינלאומי ברצועת עזה. בתמורה הבטיחו הפלסטינים לבטל אחת ולתמיד את סעיפי האמנה הפלסטינית הקוראים לחיסול מדינת ישראל. לשם כך התכנסה המועצה הלאומית הפלסטינית בעזה בנוכחות הנשיא קלינטון, אולם לא פורסם נוסח חדש של האמנה שאינו כולל את הסעיפים הקוראים לחיסול ישראל. בטרם הוקדמו הבחירות ביצעה ממשלת נתניהו רק חלק קטן מהנסיגה שלה התחייבה, כאשר נתניהו מציג את מדיניותו על ידי הנוסחה:
תקופתו של נתניהו התאפיינה בהתמקחויות ארוכות על נסיגות ו"פעימות" של אחוזים בודדים מהשטח. בימיו לא חלה פריצת דרך משמעותית בתהליך כמו בימי רבין, אך גם לא החמרה ביחסים כמו בימי ברק.
במהלך תקופת כהונתו, חל קיפאון במגעים עם סוריה, אף על פי שידידו האישי, המיליונר האמריקאי רון לאודר, נשלח לסוריה מטעמו. לטענת דניס רוס ומרטין אינדיק, טיוטה שהציג לאודר בשמו של נתניהו לסורים, וזכתה להסכמתם, כללה נסיגה מרמת הגולן לקו על בסיס גבולות 1967, כאשר תוואי הקו המדויק ייקבע לאחר משא ומתן בין הצדדים. לטענת נתניהו, הוא התעקש על כך שקו הגבול יעבור קילומטרים מזרחה יותר.
התחום הביטחוני.
בתקופת כהונתו של נתניהו כראש ממשלה היה מספר הפיגועים נמוך משמעותית בהשוואה לתקופותיהם של שני קודמיו בתפקיד, יצחק רבין ושמעון פרס, ולשני ראשי הממשלות שלאחריו, אהוד ברק ואריאל שרון. בשנת 1999, שנת כהונתו האחרונה של נתניהו, נרצחו 4 אנשים בפיגועים, המספר הנמוך ביותר מאז ראשית האינתיפדה הראשונה ועד 2008.
שהיית צה"ל בדרום לבנון המשיכה לגבות קורבנות רבים, בהם: אסון המסוקים (4 בפברואר 1997),
מות שלושה קצינים מסיירת צנחנים בהיתקלות באזור הביטחון (23 בפברואר 1997), ואסון השייטת (5 בספטמבר 1997) שבו נהרגו 12 לוחמי שייטת 13 במארב של חזבאללה בלבנון. אסון המסוקים החזיר לסדר היום הציבורי את הפקפוק שבשהיית צה"ל בדרום לבנון והיה הזרז להקמת ארגון ארבע אמהות שפעלו לנסיגה מדרום לבנון. בעקבות נפילת הקצינים הודיע יו"ר מפלגת העבודה, אהוד ברק, על התחייבותו לצאת מלבנון תוך שנה מהיבחרו, עדיף תוך משא ומתן עם סוריה. תגובתו של נתניהו הייתה האשמת ממשלת לבנון באי מוכנות לשאת ולתת על הנסיגה.
בשלהי תקופת כהונתו הראשונה של בנימין נתניהו כראש הממשלה הוא הקים את המועצה לביטחון לאומי והעמיד בראשותה את האלוף דוד עברי. הקמת המועצה נעשתה בהתאם להמלצה שניתנה במסגרת הפקת לקחים ממלחמת יום הכיפורים שלא הוצאה לפועל על ידי ראשי הממשלות שקדמו לו.
התחום הכלכלי.
נתניהו, הדוגל באסכולת שוק חופשי, העלה על נס את ערכי הכלכלה החופשית ואת ההפרטה, וחתר לממש תפיסה זו החל מכהונתו הראשונה כראש ממשלה, בכדי לחזק את הכלכלה הישראלית. לממשלתו הראשונה היו מספר הישגים כלכליים:
במהלך תקופת ממשלתו הראשונה של נתניהו, כיהנו שלושה שרי אוצר: דן מרידור, יעקב נאמן ומאיר שטרית - כל אחד למשך פרק זמן של כשנה.
עימותים והקדמת הבחירות.
תקופתו של נתניהו כראש ממשלה לוותה בחילוקי דעות חריפים בציבור. אנשי השמאל ייחסו לו חלק ביצירת האווירה שאפשרה את רצח רבין, ויש הטוענים שהתנגדותם לו גברה בעקבות התרסותיו כלפי השמאל או חלקים ממנו. יש הטוענים כי השנאה כלפיו היא המשך השנאה של השמאל כלפי מנהיגי ימין כגון ז'בוטינסקי, בגין, שרון ושמיר. ויש הטוענים שהוא שיבש וסיכל את תוכניות השלום של השמאל.
הופעתו התקשורתית המלוטשת הביאה לו תומכים, אך היחסים בינו לבין כלי התקשורת היו עכורים, והוא האשים אותה בהתנכלות לו. עם זאת, נתניהו זכה לאהדה רבה בחוגי החרדים והימין המסורתי.
במהלך שנות כהונתו כראש ממשלה, ואחר כך כשר החוץ, קידם נתניהו את היחסים עם הימין הנוצרי השמרני האמריקני. פעילות זו, שלוותה בידידות אישית חמה בין נתניהו, ג'רי פאלוול ומנהיגים אחרים מהימין הנוצרי, עוררה ביקורת בישראל ובקרב יהדות ארצות הברית.
יחסיו עם בעלי בריתו הפוליטיים לֻוּוּ לעיתים בחריקות וצרימות. הגיבוי שלא נתן לשר האוצר, דן מרידור בנושא "רצועת האלכסון" הוביל להתפטרות האחרון, כעבור שנה מכניסתו לתפקיד. שר החוץ דוד לוי פרש בגלל התנגדותו לצעדים הכלכליים שנקט נתניהו בראשית 1998, אך גם בגלל יחסים אישיים רעועים עמו.
אחרי חתימת הסכם ואי, ביצעה ממשלתו חלק קטן מהנסיגה שהתחייב לה. ההסכם גרם לאכזבה מצד חלק מאנשי הימין בקואליציה. מפלגות השמאל נמנעו מלספק לו רשת ביטחון בנימוק שהוא מתמהמה ביישום מלא של ההסכם ובעקבות מתקפה שלו עליהן עם שובו מהוועידה. ההתמרמרות על התנהלותו האישית הובילה לאובדן תמיכת גורמי מרכז בו. סיבות אלה הובילו להקדמת הבחירות לכנסת החמש עשרה ולראשות הממשלה.
ב-21 בדצמבר 1998, הצביעה הכנסת על פיזורה בקריאה שלישית ועריכת בחירות טרם סיום תאריך כהונתה המקורי, כמחווה של הבעת אי-אמון בנתניהו, על אף ניסיונותיו למנוע את ההצבעה ולגרום לדחייתה.