בערב חורפי אחד ב-2003 נפגשו כמה חברים ירושלמים בסטודיו של יוגב שטרית ובלי הכנות מיוחדות החלו לנגן. בתום הג'אם סשן היה ברור לכל הנוכחים - להקה חדשה נולדה בישראל.

החברים הללו מנו את יובל גרשטיין (גיטרה), דויד חכם הרסון (חצוצרה), אריק לוי (סקסופון), אורי וינוקור (באס) ויוגב שטרית (תופים). כל אחד מהחמישה הביא את מקורותיו הוא למוסיקה - ג'אז, Fאנק, סול, קצת אלקטרוניקה וקצת השפעות מזרחיות. גרשטיין ושטרית שיתפו פעולה בלהקת Fאנק-ג'אז כזו בשם חם ומחמם בום, לאורי וינוקור עבר בלהקת קאברים בשם אוגוסט, שסולניתה היתה מרב סימן-טוב.

20 סשנים הוקלטו, ובין אילתור אחד למשנהו, נמצאו הקטעים שלעתיד יגובשו ויעובדו לחומר המוקלט הרשמי. לאחר כמעט שנה של נגינה ללא הופעות, החליטה הלהקה להתקדם צעד אחד קדימה. הלהקה בחרה לשמה את הסלנג הירושלמי "קולולוש". באחת מהופעותיה בחאן הירושלמי, עלה לבמה ראפר בשם Rebel Sun ו"העיף" את הקהל. רבל סאן, הוא ג'ואל קווינגטון, הגיע לישראל ממרילנד עם אשרת תייר ב-1999, התאהב בארץ והחליט להשאר בה. הוא פעל בהרכב ראפרים ירושלמי בשם Live Audio Sound. אף אחד בלהקה, למעט וינוקור, לא פגש בו מעולם. במשך חצי שעה הופיע פריסטייל והחיבור ביניהם נשא פרי.

ביולי 2004 הקליטה הלהקה את אלבום הבכורה הנושא את שמה. באלבום 11 שירים מקוריים, בהם Mehubav המסמפל קטעים מהשיר המפורסם My Favorite things. רבל סאן משתתף בארבעה קטעים, השאר אינסטרומנטלים. בפברואר 2005 נערכה הופעת ההשקה של האלבום במועדון המעבדה בירושלים לעיני קהל של 300 איש. הסינגל Conception הורד משרתי אתר הלהקה ע"י יותר מ-3000 גולשים.

בסוף 2005 צורף ללהקה הטרומבוניסט ירון אוזנה (התפוחים). באותה שנה נקלע רבל סאן לתסבוכת ביורוקרטית עם המדינה כאשר זו טענה שאשרת התייר שלו פגה והוא מועמד לגירוש. במסגרת המאבק להסדרת מעמדו של הזמר בארץ, הקליטה הלהקה שיר מיוחד בשם Fight Rebel Sun, בו הצטרפו ללהקה קוואמי, שאנן סטריט (הדג נחש), קאשי, סגול 59 ו-MC קרולינה (פאנסט). הסינגל כולל שלוש גרסאות לשיר המקורי, בהן רמיקס של אורי שוחט ושל Bubble. במאבק עצמו ניצח רבל סאן את הביורוקרטיה וקיבל אשרה להשאר בארץ.

בהופעה אחת שערכו ב-2007 בפני בני נוער במחנה אומנויות, נוצר כשל במערכת החשמל שלא איפשר חיבור למערכת ההגברה והתאורה בו זמנית. התוצאה - החלטה לוותר על התאורה ולקיים את ההופעה בחושך מוחלט. הופעה זו הוקלטה ויצאה מאוחר אותה שנה באי.פי מיוחד בשם Live In The Dark, שנמכר בלעדית בהופעות.

בראשית 2008 יצאה הלהקה לחודשיים של הקלטות והופעות בארה"ב. לטובת הקלטת אלבומם השני Elements of Sound נעזרה במפיק דיויד אייבורי (שעבד עם הרוטס ואריקה באדו). באלבום משתתף זמר הג'אז הנודע באני סיגלר בשני קטעים והפרקשניסט פאבלו בטיסטה (שניגן גם עם אלישיה קיז).

ב-2010 נטלו חלק בפרוייקט סינסתזה האמנותי, בו ביצעו קטע בשם "זו העונה" שהלחין מיכאל וולפה.