בבחירות הכלליות שנערכו בשנת 2003 זכתה שינוי להישג מדהים וזכתה ב-15 מנדטים.
המפלגה, בראשותו של טומי לפיד, הצטרפה לקואליציה שהקים שרון. לפיד מונה לסגן ראש הממשלה ושר המשפטים, אברהם פורז מונה לשר הפנים, יהודית נאות מונתה לשרה לאיכות הסביבה, אליעזר (מודי) זנדברג מונה לשר המדע (ולאחר מכן גם כשר התשתיות), ויקטור בריילובסקי החליף את זנדברג כשר המדע ואילן שלגי, שכיהן גם הוא כשר המדע, ולאחר פטירתה של יהודית נאות, התמנה לשר לאיכות הסביבה.
יוסף פריצקי מונה לשר התשתיות הלאומיות אך נאלץ לסיים את תפקידו בטרם עת, ב-13 ביולי 2004, כאשר לבקשת יושב-ראש מפלגתו, טומי לפיד, פוטר על ידי ראש הממשלה, משום שפריצקי הודה בכך שביקש "לתפור תיק" ליריבו הפוליטי במפלגה, שר הפנים אברהם פורז. הקרע בין פורז לפריצקי גלש לפסים מכוערים בשנת 2002, כשנוצר קשר בין ח"כ פריצקי והחוקר הפרטי יעקב אשל, שהקליט חלק מהשיחות בין השניים. בשיחות סיפר פריצקי על רצונו "לתפור תיק" לפורז. פרקליטות המדינה קבעה כי במקרה זה לא נעברה עבירה פלילית. בעקבות אירועים אלה פרש פריצקי מ"שינוי", והפך לסיעת יחיד בכנסת ושמה "צל"ש - ציונות ליברליות שוויון.
בהצבעה על תקציב המדינה שנערכה ב-1 בדצמבר 2004 הצביעו חברי הכנסת מטעם שינוי נגד, כיון שלטענתם כלל התקציב תוספות שונות למגזר החרדי. לאחר הצבעה זו פיטר ראש המממשלה, אריאל שרון, את שרי שינוי והמפלגה עברה להנהיג את האופוזיציה.