בשנת 1998 ובראשית 1999 ניסתה שינוי בראשות פורז למצב את עצמה כמייצגת בעיקר את מעמד הביניים, תוך התמקדות בצימצום המעורבות הממשלתית במשק ואת נטל המס, אולם לניסיון זה לא היה כל ביטוי במשיכת קהלי מצביעים, ולקראת הבחירות לכנסת ה־15 נראה היה שהמפלגה לא תעבור את אחוז החסימה ותיעלם מהמפה הפוליטית. עם זאת, עמדותיו ומאבקיו של אברהם פורז בתחומים השונים, כמו גם זהירותו המדינית והעובדה שלא היה מזוהה בציבור עם הסכמי אוסלו, זכו לתמיכתו של העיתונאי הוותיק והכריזמטי יוסף (טומי) לפיד, שנודע מזה שנים רבות בעמדות מרכז ליברל-קפיטליסטית ואף שימש מזכ"ל מפלגת המרכז הליברלי (שחברה לשינוי בבחירות לכנסת ה־12). לפיד זכה באותה תקופה לחשיפה ניכרת ואהדה ציבורית רחבה בזכות השתתפותו הקבועה כחבר פאנל קולני בתוכנית האקטואליה השבועית "פופוליטיקה" בערוץ 2 (קודם לכן "פופוליטיקה" בערוץ 1). בעקבות מגעים של הרגע האחרון בין פורז ללפיד, הסכימו השניים על שילוב כוחות והתמודדות שינוי בראשות "לפיד ופורז", כאשר לפיד, שאינו חבר מפלגה, במקום הראשון, ופורז, יו"ר המפלגה, במקום השני. כחלק מההסכם, שאושר על ידי רוב מוחץ במועצת שינוי, הורכבה רשימת מועמדים לכנסת המבוססת בעיקר על אנשי שינוי, אולם במקומות הריאליים הוצבו בעיקר אישים מטעמו של לפיד, ובכלל זה חה"כ אליעזר זנדברג, יוצא מפלגת הימין המתפרקת צומת, במטרה למצב את שינוי החדשה כמפלגת מרכז ולא שמאל. הרשימה לכנסת התכנתה "שינוי – התנועה החילונית", וניהלה מסע תעמולה שהתמקד כמעט כולו במלחמה בכפייה דתית, בהקצבות לחרדים ובדרישה לגייסם לצה"ל. היא הבטיחה שלא להצטרף אלא ל"ממשלה בלי חרדים".
המהלך, שמטרתו הייתה להבטיח את מקומה של שינוי בכנסת, הצליח מעבר למצופה, ורשימת שינוי החדשה בראשות לפיד זכתה בשישה מנדטים, מתוכם שניים (אברהם פורז ויהודית נאות) מקרב אנשי מפלגת שינוי הוותיקים. בעקבות ההישג הצטרפו רבים מתומכי שינוי החדשים כחברי המפלגה, וביניהם גם לפיד, שהתמנה ליו"ר המפלגה. מתוך הבנת חשיבות הבטחת המפלגה לבוחריה, בעיקר לאור כישלונן של מפלגות מרכז אחרות בעבר לשרוד יותר מכהונה בודדת, סירבה המפלגה להשתתף בקואליציה של אהוד ברק, שכללה את ש"ס ובראשיתה גם את יהדות התורה. שינוי נותרה באופוזיציה תוך שהיא מעניקה לממשלת ברק רשת ביטחון בנושאים מדיניים (בעיקר על ידי הימנעות בהצבעות קריטיות). השבר שחווה שמאל הישראלי בעקבות כישלון ועידת קמפ דייוויד (2000) ופרוץ האינתיפאדה השנייה, הביא לזינוק משמעותי בתמיכה הציבורית של שינוי, שכמפלגת אופוזיציה לא נתפשה כאחראית למצב, וכמפלגת מרכז הסתמנה לרבים בקרב מאוכזבי השמאל כאלטרנטיבה אלקטורלית יחידה. תרמו לכך גם הישארותה של שינוי באופוזיציה גם לאחר הבחירות המיוחדות לראשות הממשלה בהן ניצח אריאל שרון את אהוד ברק, והקפדתה היתרה על משמעת סיעתית בכנסת בהתאם לעמדותיהם ולמרותם של לפיד ופורז.
הכנסת ה־16.
בבחירות לכנסת השש עשרה ב־2003 קיבלה שינוי 15 מנדטים והייתה למפלגה השלישית בגודלה בכנסת. הפעם, צורפה שינוי לקואליציה, ואילו ש"ס ויהדות התורה נותרו בגללה באופוזיציה, לראשונה מאז הקמת המפלגות החרדיות. בין שינוי לבין המפלגות החרדיות התנהלה מלחמת תעמולה, וחילופי הדברים מעל דוכן הכנסת, בתקשורת ובביטאונים המפלגתיים, היו חריפים מאוד.
כדי לאפשר את חבירתן לקואליציה אחת נאלצו גם שינוי וגם המפד"ל לעשות ויתורים. ההחלטה המשמעותית ביותר שבוצעה לפי ההסכם הקואליציוני היא הקיצוץ הדרסטי בקצבאות הילדים, שהיוו מקור הכנסה חשוב למשפחות חרדיות וערביות מרובות ילדים.
משרד הדתות נסגר, אולם התקציבים שהועברו דרכו למוסדות דת הועברו דרך משרדים אחרים, אם כי חל בהם קיצוץ מסוים. בתי הדין הרבניים הועברו לפיקוחו של משרד המשפטים, שבראשו עמד יוסף לפיד. ביטול חוק טל המאפשר את דחיית גיוס בחורי הישיבות התקדם בעצלתיים, ולבסוף, לאחר חזרת החרדים לקואליציה ופרישת שינוי, ירד מסדר היום כליל. עם זאת, העבודה על חוק ברית הזוגיות, שנועד לאפשר נישואים אזרחיים, הובילה להעלאת הנושא לסדר היום, אף שגם היא לא הניבה פירות. גם חוגים דתיים הביעו תמיכה בהנהגת מסלול של "זוגיות", שיקביל לנישואים ההלכתיים, ויאפשר לפסולי חיתון, ואולי לא רק להם, להקים תא משפחתי המוכר על ידי המדינה.
כחצי שנה לאחר הבחירות לכנסת ה־16 נערכו הבחירות לרשויות המקומיות, וגם בהן זכתה שינוי להצלחה בלתי מבוטלת, כשכמה עשרות מחברי שינוי נבחרו למועצות ערים ולמועצות מקומיות בכל רחבי הארץ. שניים מהם אף נבחרו לתפקיד ממלא מקום ראש העירייה – צבי דהרי בחיפה ואלמוג בורשטיין (שכיהן לפני כן כמנכ"ל המפלגה) בהוד השרון. יחד עם זאת, נכשלה המפלגה במספר מוקדים בהן ביקשה להעמיד מועמד לראשות העיר, כמו בעיר באר־שבע, שם לא הצליח המועמד מטעמה לגבור על ראש העיר המכהן, יעקב טרנר. בשל הניסיון להתפרס בערים רבות ברחבי הארץ וכתוצאה מהשקעה כספית מסיבית במועמדים שלא עמדו בציפיות האלקטורליות מהם, סיימה המפלגה את הקמפיין המוניציפלי בגירעון.
אולם, במשך השנים חל כרסום בהישגי המפלגה: משרד הדתות נפתח מחדש (אם כי סמכויותיו מצומצמות), והתקציבים למוסדות דת ולזרם החינוך החרדי הוגדלו במידה משמעותית. לעומת זאת, קצבאות הילדים לא חזרו למתכונתן הקודמת.
עם תחילת המשא ומתן הקואליציוני עם סיעת יהדות התורה, בעקבות פרישת מפלגות הימין מממשלת שרון עקב תוכנית ההתנתקות, גרמה לכינוס ישיבת מועצת שינוי, שבו נתבקשה להכריע בשאלה האם צריכה שינוי לשבת עם החרדים בממשלה. בתמיכת ראשי המפלגה כולם, קיבלה המועצה את ההחלטה להישאר בממשלה בכל מקרה. בהצבעה שנערכה בכנסת ב־1 בדצמבר 2004 הצביעו שרי "שינוי" נגד הצעת תקציב המדינה לשנת 2005, שכללה תוספות לחרדים, ובעקבות זאת פוטרו מהממשלה, והמפלגה חדלה להיות חלק מהקואליציה.
לפני ההצבעה על תקציב שנת 2005 הצהירו ראשי שינוי שוב ושוב כי לא יתנו ידם לחוק התקציב, בשל 290 מיליון שקלים שהופנו לחרדים. אחר לחץ גדול שהופעל עליהם מחוגי השמאל שלא למנוע את יישום תוכנית ההתנתקות ולאחר שהובטחו 700 מיליון שקלים למטרות הקרובות ללבה, הסכימה המפלגה לבסוף לתמוך בתקציב מחוץ לקואליציה.
בעקבות החלטה זו הואשמה שינוי ב"זנות פוליטית" ובכך שהיא לא שונה מהמפלגות החרדיות שנגדן היא יצאה על סחיטת תקציבים למטרותיהן הסקטורליות. האשמות אלה לוו בחילופי דברים קשים בין טומי לפיד וחברי מרצ־יחד: בעיקר יוסי ביילין וזהבה גלאון. מנגד, ראשי שינוי הצדיקו את המהלך בטענות שחובתם כמפלגה אחראית היה לתמוך בתקציב כדי לקדם את ההתנתקות, ושאין פסול בכך שהם הפעילו את כוחם על מנת להפנות משאבים ליעדים ראויים.
הבחירות לכנסת ה־17.
המעמד והאמון הציבורי של לפיד ופורז התכרסם. המועמדים הבולטים שיכלו להחליפם לא עשו זאת: אוריאל רייכמן עבר למפלגת קדימה, יוסף פריצקי נתפס בקלקלתו והורחק מהמפלגה, יהודית נאות נפטרה ואליעזר זנדברג בחר שלא להתמודד נגד לפיד בבחירות הפנימיות, למרות שיד ימינו הפוליטי, נחמיה דורון, התמודד נגד פורז.
הקמתה של מפלגת קדימה בראשות ראש הממשלה אריאל שרון, אשר פנתה לקהל הבוחרים של שינוי, דרדרה את שינוי למצב שהיא עלולה לא לעבור את אחוז החסימה ולהיעלם מהמפה הפוליטית. גורם נוסף לכך היה דחיקתם של נושאי דת ומדינה, בהם התמקדה שינוי, לשולי סדר היום הציבורי עקב הצלחתה היחסית של המפלגה להרחיק את המפלגות החרדיות ממוקדי השלטון, ועקב השינויים במצב הביטחוני־מדיני.
ב־12 בינואר 2006 נערכו בחירות מקדימות בשינוי לקראת הבחירות לכנסת השבע עשרה, בהן הצליח רון לוינטל לזכות במקום השני על חשבון אברהם פורז. תוצאות הבחירות המקדימות גרמו למשבר חמור במפלגה. פורז העדיף שלא להתמודד על מקום בהמשך הרשימה, והחליט לפרוש משינוי יחד עם עוד שישה מחברי הכנסת של שינוי, ולהקים מפלגה חדשה, מפלגת חץ. בנוסף, פרשו גם חברי הכנסת אליעזר זנדברג ונחמיה דורון והקימו את סיעת "הבית הלאומי".
לפיד, אשר נבחר ברוב דחוק למקום הראשון ברשימה, זעם על התוצאות, וב-25 בינואר כינס מסיבת עיתונאים ובה הודיע על התפטרותו מתפקיד היו"ר ופרישתו ממפלגת שינוי. איתו פרשה גם אראלה גולן, שנבחרה למקום החמישי ברשימה, ושניהם הצטרפו למפלגת חץ שהקים פורז. מאוחר יותר פרשו גם יגאל יאסינוב, שעבר למפלגת ישראל ביתנו והפעיל המפלגתי המרכזי איקי אלנר, שהיה יד ימינו של לוינטל.
בעקבות זאת, נותרו בסיעת שינוי בכנסת שני חברים בלבד, חברי הכנסת אהוד רצאבי ואילן ליבוביץ'. השניים, בהנהגתו של רון לוינטל החלו בהתארגנות לבחירות לכנסת ה־17, בסיסמה: "שינינו את שינוי - נשנה גם את המדינה". שינוי פתחה במאמצי תעמולה, שכללו תשדיר שהוגדר על ידי נשיא בית המשפט העליון, אהרן ברק, כ"אחד המקרים החריגים בהם הפרסום מזעזע את אמות הסיפים של הסובלנות ההדדית, כי יש בו דמיון מעורר חלחלה לתעמולה אנטישמית" בתשדיר נראים חרדים אשר נתפסים על רגלו של חילוני ומפריעים לו בהליכתו, ונעלמים כלא היו עם שלשול הפתק של שינוי לקלפי. הסקרים שלפני הבחירות ניבאו ששינוי לא תעבור את אחוז החסימה ואכן כך קרה.
בעקבות עזיבת חברי מפלגה רבים, העובדה שהמפלגה לא הצליחה לגייס אישיות מרשימה שתעמוד בראשה, מריבה על המקום הראשון ברשימה שהגיעה לבית המשפט וסירובם של ותיקי המפלגה לקבל את השינוי הפנימי שהכתיבה להם מועצת המפלגה, השיגה שינוי בבחירות רק 4,907 קולות (0.16%) ואיבדה את מקומה בכנסת. היא המשיכה את פעילותה כתנועה חוץ-פרלמנטרית.
מאז 2006.