בשנים אלו המשיכו ההתרחשויות המדיניות לעמוד בראש סדר היום הלאומי. המשא ומתן עם הפלשתינאים נמשך, אם כי ידע עליות ומורדות נוכח פיגועי התאבדות המוניים. ב- 25.2.94 ברוך גולדשטיין, תושב קריית ארבע, רצח מוסלמים במערת המכפלה שבחברון, וגרם לפציעתם של עשרות. המתח באזור גבר.
ב - 4.5.94 נחתם "הסכם קהיר", שאחד מנושאיו קבע את העברת "עזה ויריחו תחילה" לשליטה פלשתינאית. ב- 26.10.94 נחתם הסכם שלום עם ממלכת ירדן, שהוסיף נדבך לתהליך ההתפייסות בין העמים.
אולם תהליך זה קיבל מכות אנושות, שכן, בשנים 96' - '95 אירעו פיגועי טרור קשים (אוטובוס קו 5 בת"א וקו 18 בירושלים), ופיגועי התאבדות (בית ליד, דיזנגוף סנטר ואשקלון), שהביאו למותם של עשרות ישראלים.
אירוע שיא, בבחינת טראומה לאומית, היה רצח ראש הממשלה, יצחק רבין, ב - 4.11.95, על-ידי מתנקש יהודי, יגאל עמיר, בתום עצרת המונים למען השלום. ב - 11.4.96 החל מבצע "ענבי זעם", כתגובה לירי מאות טילי קטיושות, לעבר ישובי הצפון.
ב- 29.5.96 חל מהפך פוליטי עקב הבחירות בישראל, שהביא את מפלגת הליכוד לשלטון, כשבראשה (ראש ממשלה) בנימין נתניהו. לקראת סוף שנת 1996 התרחשו אירועי דמים בשטחי יהודה, שומרון וחבל עזה, בעת ששוטרים פלשתינים ירו והרגו חיילי צה"ל ושוטרים. אירועים פרצו לאחר פתיחת "מנהרת הכותל" ב - 23.9.96.
המציאות המדינית החדשה, שבה הושג הסכם שלום עם הפלשתינאים, הביא לשידוד מערכות וטיפול מסיבי של משטרת ישראל, נוכח אירועים חבלניים רבים וקשים. חתימת "הסכמי אוסלו" הביאה להקמת המחוז השישי - מחוז ש"י (שומרון ויהודה), שנועד לתת מענה טוב יותר בנושאי בטחון וסדר ציבורי בשטחי איו"ש.
ההיערכות המחודשת של צה"ל באזורים אלו הטילה על המשטרה את האחריות לביטחון פנים במרחב לכיש, והובילו להקמת מרחב שמשון. מפקדת מג"ב דרום נחלקה למג"ב ת"א מרכז ולמג"ב דרום, שתרמו לייעול מוט השליטה. הפיגועים הקשים הביאו את פיקוד המשטרה להיערך בפריסה נכונה בשטח ברמת המודיעין, כדי לסכל את הפיגועים ולצמצם את הנזק.
המשטרה המשיכה בהשקעת מאמצים רבים בפעילותה במשימותיה הקלאסיות, ובעיקר במלחמה בפשיעה, בנגע הסמים, בתאונות הדרכים ובשמירה על הסדר הציבורי.
רצח ראש הממשלה, יצחק רבין, הביא לחשיבה מחודשת בנושא אבטחת אישים, תוך עבודה משותפת עם זרועות הביטחון השונות. המשטרה טיפלה בתקופה זו בפרשיות שונות, כדוגמת פרשיית "האזנות הסתר", ופרשת עוזי משולם וחקירתם של ראשי רשויות רבות, שנחשדו לכאורה בפלילים. בתחילת 1995 הוקמה היחידה לשיטור קהילתי, שמטרתה הצבת האזרח והקהילה במרכז הפעילות המשטרתית, תוך שילובן של הרשויות המקומיות.
במקביל, נמשכה המדיניות של שיפור הטיפול בפרט, כולל בשכר השוטרים. מערך ההדרכה פותח ושוכלל, ותוגברה מערכת הגיוס למבצע "גיוס 2000 ", שמטרתו העלאת רמת המגויסים לשורות המשטרה. המיחשוב קיבל תנופה, והורחבה פריסת התוכנה והחומרה בנושאי כוח-אדם. החל תהליך של הצעדת המשטרה לקראת שנת 2000. נערך רכש מסיבי של אמצעים וכלים, כדי לתת מענה טוב יותר כנגד תופעת פיגועי התאבדות והשלטת סדר ציבורי. בשנת 1995 הוקם מנהל התנועה (מנ"ת), שתפקידו לרכז את נושא התנועה העירונית והבינעירונית, תוך פיקוח משטרת התנועה הארצית.
במהלך 1996 החל במשטרה תהליך לתכנון אסטרטגי כולל לשנים הקרובות, ובתחילת 1997 קיבלו המלצות הצוותים השונים את אישור המפכ"ל והשר לביטחון פנים.
במהלך שנת 1997 המשיכה משטרת ישראל בהשקעת מאמץ מתמשך נוכח גל הפשיעה הגואה ומעשי הטרור במדינה. החקירה העדינה ביותר עמה התמודדה המשטרה הייתה "פרשת בראון", במהלכה נחקרו עשרות אישים, ביניהם ראש הממשלה ושר המשפטים.
במבנה הארגוני של המשטרה חלו שינויים, עת הוקמו בו שני אגפים חדשים: אגף התנועה ואגף המודיעין, שהוקמו נוכח תאונות הדרכים וגל הפשיעה הגואה. האגפים באו לתת מענה הולם בריכוז המאמץ ובשכלול השיטות וטכנולוגיה החדשה להורדת עקומת תאונות הדרכים ועקומת הפשיעה.
בתחום בטחון הפנים, הועברה האחריות של "קו התפר" לידיו האמונות של משמר הגבול, שהחל במלאכה לאחר הכנה מדוקדקת. ככלל, רכשה המשטרה ציוד משוכלל ואיכותי ללוחמה בטרור ובפשיעה הקשה, תוך התמקדות בהתמקצעות של שוטריה. במהלך שנת 1997 התקבל במשטרה "הקוד האתי", שבא לחדד את תפיסת התפקיד וההבנה של משמעות המקצוע המשטרתי.
משטרת ישראל המשיכה להתעצם במשאב האנושי ובאמצעים הטכנולוגיים, כדי לתת מענה נוכח מטלותיה הרבות, וזאת ובאמצעות 6 מחוזותיה, 10 מרחביה וכ- 80 תחנותיה, על 25,000 שוטריה.