Nati da un nucleo eterogeneo di musicisti da strada, la formazione dei Bizantina definisce il suo nome e stabilizza la sua struttura nel 1996, in occasione della partecipazione all’Ottavo Festival On The Road di Pelago, che premia con la vittoria il neonato ensemble, ancora fortemente caratterizzato dall’impostazione acustica tipica dei basker. Tra gli otto musicisti del gruppo figurano già quattro degli attuali componenti: Michaela D’Astuto (voce), Susanna Crociani (sax, clarinetto, flauti), Marcello Melighetti (chitarra classica e acustica, mandola, buzuki), Mauro De Lillo (batteria e percussioni). Completano l'ensemble Anna Granata (voce), Mauro Citzia (contrabbasso) e Rocco Giorgi (chitarra classica).
Il successo di pubblico e di critica riscosso in questa circostanza induce la formazione a incidere i migliori brani del proprio repertorio, composto da arrangiamenti di melodie tradizionali e canzone d’autore (De Simone, Eugenio Bennato, Nuova Compagnia Di Canto Popolare) e brani originali (Pizzica della Serpe, Terra, Occhi Neri ed E’ Notte, il cui testo è liberamente tratto da una poesia di Eduardo De Filippo), che vengono raccolti nel CD E’ Notte, stampato in 1000 copie e rapidamente esaurito. La registrazione suscita notevoli consensi anche da parte della critica specializzata, e frutta ai Bizantina la vittoria al Premio Ciampi di Livorno nel 1997 e la partecipazione al Gray Cat Festival; nello stesso anno il CD viene ristampato in 12.000 copie e distribuito con la rivista Re Nudo con il titolo Mare, Sole E Luna, in cui sono inclusi come bonus track due nuove composizioni originali, Fuochi e Girapasso.
Nel 1998 i Bizantina ottengono altri prestigiosi riconoscimenti (finalisti per la Toscana alla manifestazione Arezzo Wave; partecipazione a un concerto al Palasport di Firenze con Miriam Makeba, Vinicio Capossela e Frankie Hi-NRG) e incrementano significativamente la propria attività live in Italia e all’estero (una tournée in Portogallo e una serie di concerti alle Isole di Capo Verde). Le esigenze imposte da questo confronto con palchi ampi, assai lontani dall’originale situazione “di strada”, conducono a importanti variazioni di organico (l’entrata del fisarmonicista Emiliano Benassai, tuttora parte del gruppo, e l’uscita della cantante Anna Granata) e un maggiore impegno nella composizione di brani originali. Tale repertorio viene elaborato nel corso del 1999 e proposto al pubblico nel corso delle numerose occasioni in cui i Bizantina si esibiscono (oltre a svariati concerti in Italia, effettuano una tournée di 35 date in Spagna e Portogallo e partecipano in Belgio alla rassegna Cape Sud di Mons).
La realizzazione del secondo CD, Bizantina, avviene nel 2000, in coincidenza con l’entrata del virtuoso cantante e percussionista salentino Rocco Zecca (voce e percussioni), il cui contributo risulta particolarmente apprezzabile negli arrangiamenti della pizzica tradizionale Santo Paulo Meo e di Pizzica Minore di Eugenio Bennato.
Il CD Bizantina raccoglie arrangiamenti di brani da tempo nel repertorio live del gruppo (Volta La Carta di De Andrè, Brigante se More e Vulesse Addiventare Nu’ Brigante di Eugenio Bennato, Imastu Kecci dei Ghetonìa) che riscuotono notevoli apprezzamenti da parte della critica ("gli omaggi alla coppia De Andrè-Bubola di Volta la carta e alla rivoluzione di Eugenio Bennato delimitano perfettamente quelle Terre di Mezzo sonore che i Bizantina propongono senza finta maniera", Daniele Bergesio, World Music), affiancati da composizioni originali (Tra Cilo e Mare, Grancassa, Prigionieri, Piccolo Tango, Ville Rupt) in cui lo stile del gruppo si caratterizza sempre più, arricchendosi di sfumature orientaleggianti e balcaniche.
Esaurite nel giro di un anno le prime 2000 copie, il CD viene ristampato con l'etichetta Radici Music in 2000 esemplari, anch'essi esauriti a seguito di un intenso periodo di esibizioni dal vivo. All'indomani dell'uscita del CD, la formazione vede infatti consolidato il proprio spessore tecnico con l'ingresso di Samuele Venturin (fisarmonica, violino e chitarra) e Michelangelo Zorzit (basso e chitarra), e si dedica a un un accurato lavoro di riarrangiamento dei propri brani, alcuni dei quali sono raccolti nel CD Un Saluto Di Speranza (2002), stampato in 2000 copie e distribuito dalla Coop nell'ambito di una raccolta fondi per la costruzione di un ospedale in Chiapas. I brani riarrangiati sono presto affiancati da nuove composizioni, a cui contribuiscono in misura significativa gli elementi recentemente acquisiti dal gruppo, che propone il repertorio così rinnovato in svariati festival in Italia (Etnofest al Saschall di Firenze, Venezia Suona,trasmesso da Rai Tre, Festival di Musica Classica Umberto Giordano - Lago Maggiore, Musicastrada - PI, SolidarRock - MI, Isola Folk - BG, Tarantafest - CT) e all'estero (Festival International de la Musique Universitaire di Belfort - Francia, edizioni 2002 e 2004).
Il terzoCD, Zahir, registrato nel 2004 e stampato in 2000 copie, propone un brano tradizionale e dieci composizioni originali, che spaziano da ritmi balcanici a una percussività vagamente afro, dalla morna capoverdiana alla ricchezza armonica della canzone napoletana, frutto di una raggiunta maturità compositiva ed espressiva che vede compenetrarsi le individualità del gruppo in un lavoro corale estremamente accurato. La frequenza dei concerti, la partecipazione a svariati festival (La Notte della Taranta, Martignano - LE, Festival Festival des Culture et Traditions - F, Set Sois Set Luas, S.Maria de Feria - P; Tarantafest - CT) e alla compilation Musichetnia, stampata in 30.000 copie con il patrocinio della Regione Puglia, e le favorevoli recensioni apparse su World Music, La Nazione, Re Nudo, Il Corriere di Firenze facilitano la diffusione del CD, di cui sono state attualmente vendute 1.000 copie.
Dalla collaborazione con il produttore Sergio Salaorni, nasce nel 2006 l'idea di realizzare una raccolta che include, oltre ai migliori brani del gruppo, cinque bonus track. Di questi cinque brani, tre sono composizioni originali: Salomè (Zorzit - De Lillo - D'Astuto), impreziosita da un solo del virtuoso sassofonista Daniele Sepe, Morgana (Zorzit) e Ninna Nanna Di Cuscione (Zorzit), sul testo di una ninna nanna tradizionale còrsa. Anche i restanti due brani Stonde d'invernu e Vulerebbe sono un omaggio alla Corsica, trattandosi di reinterpretazioni di canzoni originali de L'Arcusgi, una formazione prevalentemente vocale di Bastia, che partecipa attivamente alle registrazioni.
L'uscita della raccolta coincide con l'ingresso di due nuovi elementi, il percussionista Michele Lovito e la seconda voce Anna Maria Iorio, grazie ai quali il gruppo recupera alcuni aspetti dell'impostazione originale, più orientata ad una dimensione acustica e vocale.
Parallelamente al lavoro discografico, il gruppo si dedica alllo spettacolo teatrale Orlando Tarantato, nato da un'idea di Michelangelo Zorzit e rappresentato per la prima volta nel 2007. Si tratta di un musical ambientato nella dimensione favolistica di un teatro di burattini (i cosiddetti "pupi siciliani"), che allude giocosamente al contemporaneo incontro-scontro tra cultura occidentale e mediorientale, deridendo, nelle figure di Carlo Magno e Gano di Maganza, ogni governante che alimenti le conflittualità per un tornaconto personale. Sette attori-cantanti, nelle vesti dei paladini di Francia e dei loro rivali saraceni, interpretano 16 brani, in parte composti per lo spettacolo e in parte selezionati tra i migliori brani dei Bizantina, ed eseguiti dal gruppo stesso, in scena nella formazione completa.