Teatr Tańca Nie Tylko Flamenco powstał w wyniku wieloletniej pracy i poszukiwań artystycznych tancerki i choreografa Małgorzaty Matuszewskiej.

W 1998 r. Małgorzata Matuszewska stworzyła swój pierwszy spektakl "Al.-Andalus"  w którym  poezja F.G. Lorki przemieniła się w pieśni, oparte na rytmach flamenco, dzięki muzyce specjalnie skomponowanej na potrzeby przedstawienia. W spektaklu wzięli udział znakomici wykonawcy muzyki klasycznej i hiszpańskiej. "Al.-Andalus"  został zaprezentowany na festiwalu "Dni Federica Garcii Lorki" w Teatrze Rozmaitości w Warszawie w 1998r.
W 2000r. po raz pierwszy pojawia się nazwa Teatr Tańca Nie Tylko Flamenco. W skład ówczesnego zespołu wchodzą, oprócz Małgorzaty Matuszewskiej, dwie aktorki : charakterystyczna Magdalena Gnatowska i, zajmująca się zawodowo tańcem, Anna Iberszer.

Z udziałem tego składu artystek powstały dwa spektakle, oba sponsorowane przez Instytut Cervantesa w Warszawie. W 2000r. "Sólo Compás - Tylko rytm", wystawiany w offowym warszawskim Teatrze Academia został również zaprezentowany na  "Warszawskim Wieczorze Tańca i Ruchu" (Teatr Mały w Warszawie) oraz na festiwalu "Małe Formy Teatralne 2001" (Teatr 2 Strefa w Warszawie). W 2002r. spektakl "Camille Claudel - Kyojo", przygotowany na zamówienie Centrum Sztuki Współczesnej w Warszawie do prezentacji  w ramach IX Międzynarodowych Spotkań Sztuki Akcji "Rozdroże 2002", poświęconych sztuce hiszpańskiej.

W  spektaklach "Sólo Compás - Tylko rytm" i "Camille Claudel - Kyojo" środki wyrazu charakterystyczne dla sztuki flamenco zostały zmiksowane z elementami tanga argentyńskiego, w pierwszym wypadku, japońskiego tańca butoh, w drugim. Gościnny udział wykonawców nowych styli wzbogacił oba przedstawienia, w szczególności kreacja japońskiego tancerza Atsuchi Takenouchi w "Camille Claudel - Kyojo". Poszerzyła się również paleta muzyczna. Osnową dla choreografii "Sólo Compás - Tylko rytm" była płyta folkowego TAM TAM Project . W "Camille Claudel - Kyojo" nowe brzmienie zostało osiągnięte dzięki pojawieniu się fortepianu i saksofonu. Muzyka do tego spektaklu, podobnie jak w "Al.-Andalus", została skomponowana specjalnie na potrzeby przedstawienia przez Marka Walawendera.