A zenekar megalakulásának hivatalos dátuma 1999. január 2. Három ceglédi zenekar - az Artéria, a Space Box és a Fear of Silence - tagságából jöttek össze a srácok, akkor még énekest keresve. Mindhárom együttes kisvárosi koncertjein ott ugrabugrált egy hosszú barnahajú lány, nagy feltűnést keltve maga körül. Tehát már nem voltak idegenek egymásnak, amikor '99. január 1-én hajnalban az akkor még rendőrként dolgozó Terecskei Rita igazoltatta a szilveszteri buliból hazakacskaringózó autót, aminek Sidi, Gabszi, MikC és Doni voltak az utasai. Rita elengedte a fiúkat, ezért (akkor persze még csak viccből) énekesnőjükké fogadták. Másnap esteegy ceglédi szórakozóhelyen Sidi és Gabszi meglátta Ritát, miközben pótszilveszterezett barátnőivel, és egy Janis Joplin dallal szórakoztatta őket. Rögtön világossá vált, hogy a tiszteletbeli énekesnői titulus komolyabbra is fordulhat! Rita egy Kimnowak kazettát kapott Sidiéktől, amiről két számot kellett megtanulnia másnapra. Január 2-án a mai öt tag lépte át a ceglédi próbahely küszöbét - először Ritával kiegészülve -, és útjára indult a Zanzibar…

  A zenekar első demo felvétele 2000-ben jutott el a zenekar mai menedzseréhez, Kellermann Kristófhoz (Stofi), aki lemezszerződéshez juttatta a zenekart az EMI lemezkiadónál. A mai napig ő egyengeti a zenekar útját.

  Az első nagylemez 2001. május 16-án jelent meg "Nem vagyok tökéletes" címmel. Lendületességével már az első maxi (Nem vagyok tökéletes) kivívta mind a szakma, mind a közönség érdeklődését. A második single a "Vágyom rád" címet viselte; a középtempós, szomorkás dal egy roadmovie-szerű, sokat emlegetett videoklippel lett teljes. A dal tarolt a slágerlistákon. Ekkor a Zanzibar már a Venus zenekarral turnézott országszerte, és egyre nagyobb népszerűség fogadta őket mindenütt. Az igazi áttörést a harmadik, "Szólj már" című maxi hozta meg. A kislemez 2001 decemberében jelent meg, és 2002 tavaszára bebetonozta a Zanzibar nevet a magyar könnyűzenei palettába. A dalt az MTV Europe is a műsorára tűzte, és a 2002-es év játszási listájának összesítésében 8. helyezést ért el, a "külföldi dalok" között pedig hetekig első helyen volt. A MAHASZ eladási listáján 18 hétig szerepelt, és a VIVA televízió slágerlistáján is hamar az első helyig jutott. Mindeközben a nagylemez is egyre feljebb tört a MAHASZ hazai eladási listáján, míg végül 2002 áprilisában az első helyre került. Szinte ezzel egy időben az album aranylemez lett! Ekkorra már az első komoly szakmai díjat is a magáénak tudhatta a csapat: 2002-ben a Zanzibar "az év felfedezettje" kategóriájában Arany Zsiráf díjat kapott. Még ezen a tavaszon a BRAVO Otto díjkiosztón az év Magyar Rock zenekara lett, majd pár héttel később az EJI és a Sláger rádió "2001 új zenekara" címmel illette a Zanzibart.

  Már 2002-ben kezdtek megszületni az új dalok a második nagylemezhez, és a folyamatos koncertezés mellett stúdióba vonult a zenekar, hogy rögzítse a már sokak által nagyon várt második albumot. A lemez 2002. november 16-án jelent meg "Ugyanaz vagyok" címmel. A "Táncolunk" című bemutatkozó kislemez - nem csak a zene, de a rendhagyó videoklip miatt is - hamar a figyelem középpontjába került. A Magyarországon eddig még nem használt technikai módszerekkel rögzített klipet az MTV Europe is a műsorára tűzte. Ezt követően az együttes - 2003 egyik nagyon hideg februári hétvégéjén - rögzítette következő videóját az új maxihoz "Szerelemről szó sem volt" címmel.A dal a "Szólj már" méltó utódja lett! Nemsokára a második lemez is bearanyozódott! 2003-ban a szakma és a közönség ismét komoly elismerésekkel díjazta a zenekar munkásságát: Az Arany Zsiráf díjkiosztón "Az év modern Rock albuma" az Ugyanaz vagyok lett, eMeRTon díjat kaptak "Az év felfedezett együttese" kategóriában, a BRAVO Otto-n ismét a Zanzibar lett "Az év magyar Rock zenekara", majd a Popcorn újság díjátadóján ugyanebben a kategóriában állhattak a dobogó tetejére. A Coca-Cola "Az év élő koncertje a Beach House-on" díjat adományozta a csapatnak, a Wigwam által évről évre megrendezett "Arany Nyíl" díját pedig Rita kapta az év énekesnőjeként. Még ennek az évnek a végén a Kiskegyed újság kedvenc zenekara a Zanzibar lett. Ősszel kijött a második album utolsó kislemeze "Érintés" címmel. Igazi pörgős hangulatával ideális koncert- és rádió dal lett.

  A zenekar 2003-ban több mint 150 élő koncertet adott Magyarországon, és Erdélyben is nagy sikerrel tett eleget a meghívásoknak. Év végén a Zanzibar beköltözött a régi, jól bevált próbahelyre, hogy előkészítse a harmadik lemez dalait a felvételekre. A stúdiómunkálatok 2004. január 17-én kezdődtek, és május 12-én megjelent a várva várt harmadik nagylemez "Az igazi nevem" címmel.Az első maxi "Nem szeretsz" címmel rögtön nagy port kavart a horror-videoja miatt, amely olyan hitelesre sikerült, hogy nappali játszásra "nem találtatott alkalmasnak". Így hát maradt az éjjeli játszás, nappalra pedig elkészült a video könnyedebb verziója, ami egyébként a horror sztori előzményeit meséli el. A "Nem szeretsz" így két különböző videóval rendelkezik, melyek szorosan összefüggnek egymással. A második maxi a lemezről "Az igazi nevem" A dal érdekessége, hogy az együttes a már kész lemezanyaggal vonult be a stúdióba, ez a dal mégis a stúdióban született, egy kis örömzenélés alkalmával. A szöveg is a stúdió pihenőhelyiségében íródott meg, pizzásdobozok és kávéscsészék között.

  2005 tavaszán a Zanzibar stúdióba vonult, hogy rögzítse negyedik stúdióalbumát! A várva várt végeredményt október 26-tól "Új napra ébredsz" címmel már bárki meghallgathatja. Rita és a srácok erősebb formában vannak, mint valaha! A lemez első slágere, az "Ilyen az élet" nagyon pozitív viszhangra talált a rádiókban. A következő kislemez egy "Szólj már"-szintű nagy dobás lesz! A modern, masszív, dallamos rocknak és a balladák szerelmeseinek egyaránt ínyenc csemege lehet ez az album!