כרמלה גרוס ואגנר קמה כמין הרכב צדדי זמני של ערן צור, בתקופה שבה מעט מאוד להקות חדשות קיבלו הזדמנות להקליט משיריהן. בזכות ההתמדה והעקשנות של צור וחבריו הפכה הלהקה מעוד אחת מלהקות השוליים ברוק הישראלי ללהקה שזוקפת לעצמה שני אלבומים מוצלחים והשפעה רבה על הצליל הישראלי של שנות ה-90.
כרמלה גרוס ואגנר קמה ב-1989 כשערן צור, נגן הבס בלהקת טאטו, החל להופיע כסולן בשירים משלו, חלקם כאלה שיצר עם צ'לן טאטו, יובל מסנר (ביניהם "בחצרות בחושך", "תמונה אימפרסיוניסטית" ו"כרמלה גרוס ואגנר"). את שם השיר האחרון (על שם שכנים בבית הוריו בקריות) הוא אימץ כשם זמני להרכב שליווה אותו באותה תקופה: אורי בלק (מטאטו) בתופים, אורי פרוסט (מהפליז) בגיטרה ואבשלום כספי בקלידים. צור ניגן באותה תקופה גם מחוץ לכרמלה גרוס ואגנר (עם גדעון כפן, קורין אלאל ועוד), אך עיקר זמנו הוקדש ללהקה, עם עשרות הופעות, בעיקר בדחיפתה ועידודה של יעל מרגלית, ששיווקה את הלהקה בכל רחבי הארץ ולא רק בתל אביב.
באמצע שנת 1991 הסתיימו ששת חודשי הקלטת האלבום פרח שחור, בו היה צור היוצר העיקרי. הוא כתב והלחין בין השאר את "כרמלה גרוס ואגנר", "פרפרי תעתוע" ו"עד תודבר המחלה", הלחין מילים של עמליה זיו, בין השאר ל"תמונה אימפרסיוניסטית" ו"נשים כותבות שירה", והמשיך לשמור על קשר יצירתי עם מסנר, שהלחין מילים שלו ל"רטוב וחם", "פרח שחור" ואחרים. צור וחבריו ללהקה הפיקו מוסיקלית עם ברי סחרוף וקורין אלאל האלבום עורר תשומת לב רבה, אך הצלחתו המסחרית הייתה מוגבלת.
הלהקה פעלה כל העת במקביל ללהקתו של מסנר, בלאגן. שתי הלהקות הופיעו לעיתים קרובות יחד וגם התחלקו בשירים שכתבו צור ומסנר. "החבר של המשוגע", למשל, בוצע על ידי שתי הלהקות, ו"שולחן הכתיבה", שבוצע על ידי בלאגן, הוקלט שנים לאחר מכן על ידי כרמלה גרוס ואגנר.
אחרי הוצאת האלבום פרש פרוסט (ועבר אחר כך לפלומה טוויסט ומשם לריר), ובמקומו הצטרף הגיטריסט דרור אורגד. הרכב זה הקליט ב1992- לפרויקט חידושי השירים של גלי צה"ל "שוב יוצא הזמר" גרסה ל"אלינור" (מ' ג'קי מקייטן, ל' קזנדידיס). פרוסט התארח בהקלטה כמפיק שותף וכגיטריסט. השיר יצא בדיסק שוב יוצא הזמר וגם בסינגל שהפיקה יעל מרגלית, בו נכללו גם שירים שהוקלטו בהופעה ב"רוקסן", "החפץ" ו"חצי כרמלה" (מ' ול' צור). בהופעה זו צור הציג את הלהקה כ"כרמלה גרוס ו-ואגנר", מה שהשתנה בהמשך, מסיבות של תקינות לשונית, לכרמלה גרוס ואגנר.
בהמשך 1992 הצטרפה להרכב ירונה כספי (בבס נוסף), ורם אוריון (מנושאי המגבעת) החליף את אורגד בגיטרות. פרוסט המשיך לבקר בלהקה כנגן מזדמן וכמפיק בהקלטות שלא הגיעו לאלבומים, למשל, בגרסה מוקדמת מ1994- ל"ציפורן" ובשיר שלא התפרסם בשם "יחפשו לא ימצאו".
בסוף 1994 החל צור להקליט אלבום סולו ראשון, עיוור בלב ים. מאחר שחבריו ללהקה סייעו לו בדרך לאלבום והשתתפו כנגנים בחלק מהשירים הוא צירף אותם לכותרת: "ערן צור - כרמלה גרוס ואגנר", לצד בלק, פרוסט וכספי ניגנו באלבום נגנים נוספים, ביניהם רם אוריון ומיקי הררי בגיטרות, ארקדי דוכין בקלידים ועוד. בין להיטי האלבום היו "ערב ב' כסלו", "קיץ" וגם "Rush Time", שקרדיט העיבוד בו ניתן לכרמלה גרוס ואגנר. בהופעות אחרי הוצאת האלבום ליווה את צור ההרכב האחרון של כרמלה גרוס ואגנר: מוטי ביקובסקי בגיטרה ואורי בלק בתופים. בהפקותיו הבאות של צור הלהקה לא השתתפה, אם כי מדי פעם חזרו חבריה לנגן עם צור בהופעות או בהקלטות.
ב-2000, באלבומו תכלית בתחתית, חידש צור בגרסת דאנס את "תמונה אימפרסיוניסטית". בנובמבר 2001 איחד צור את ההרכב המקורי של הלהקה (אורי בלק, אורי פרוסט ואבשי כספי) להופעות אחדות.
