A zenekart Ralph Hubert basszusgitáros hozta létre az 1980-as évek közepén. Eredetileg a „Höhe 13” nevet adta volna zenekarának, mely kifejezés a történelem első gáztámadására utal. A Mekong Delta nevet azért választotta a basszusgitáros, mert elmondása szerint egy provokatív nevet akart, ami utal az emberek szélsőséges tetteire. Mive az akkori német metal együttesek technikai felkészültségét, jóval gyengébbnek tartotta, a tengerentúli zenekarokéhoz képest, elhatározta, hogy a legképzettebb német zenészekkel fog együtt dolgozni. Hubert titokban szerette volna tartani, az együttes tagjainak kilétét, ezért a korai években álneveket használt az együttes, de a cél érdekében zenekari fotók sem készültek. Döntése hátterében az állt, hogy elmondása szerint senki sem hitte volna el, hogy német zenekar játszhat ilyen technikás zenét, másrészt szerződéses kötelezettségei is voltak a zenekar egyes tagjainak. Elsőként Jörg Michael dobossal találkozott, aki bemutatta Hubertnek a Metallica Fight Fire With Fire dalát, melynek ritmikai képletei akkoriban még szokatlannak számítottak. Ez a dal jelentette Hubert számára a kiindulópontot, aki azt javasolta, Michaelnek, hogy dolgozzon ki, minél bonyolultabb dobtémákat. Az első demón Jörg Michael mellett Jochen Schröder (ex Rage) gitáros, és Peavy Wagner (ex Rage) basszusgitáros játszott, valamint Wolfgang Borgmann énekelt. Hubert korábban olyan zenekarok mellett producerkedett, mint a Warlock, vagy a Living Death, így az utóbbi együttes két gitárosát Frank Frickét és Reiner Kelchet kérte meg a debütáló Mekong Delta album munkálataira.
A debütáló album 1987-ben jelent meg, mely egyéni felfogású thrash metalt tartalmazott, kevésbé kísérletezős módon, mint a későbbi lemezeken. Ezt követően Uli Kusch került Jörg Michael helyére. Kusch felvette a Patrick Duval álnevet, mielőtt csatlakozott volna az együtteshez. 1988-ban egy The Gnome című EP jelent meg, mielőtt nekiálltak volna a második album felvételeinek.
Kísérletezés és átmeneti feloszlás (1988-1997)
1988-ban jelent meg második lemezük a The Music of Erich Zann, melyre sokan úgy tekintenek, mint legfontosabb lemezükre. A korongon hallható Interludium (Begging For Mercy) című Bernad Herrmann átköltés eredetije Alfred Hitchcock Psycho-jában lett világszerte ismert. Ezen a korongon már nagy szerepet kapott a klasszikus zene is, mely keverése a progresszív thrash metallal később az együttes védjegyévé vált. A lemez vegyes kritikákban részesült, a zenekarnak sosem sikerült olyan széles sikereket elérniük, mint néhány európai thrash metal zenekarnak. Reiner Kelch hamarosan elhagyta a zenekart, helyére a Mark Kaye álnéven szereplő Uwe Baltrusch került. 1989-ben egy Toccata című Ep jelent meg a zenekartól, amit a The Principle of Doubt album követett. Ezt követően Fricke elhagyta a zenekart, hogy más zenei stílusokban is kipróbálhassa magát. Hubert úgy döntött, hogy nem vesz be helyére senkit, így Baltrusch egyedül gitározott a továbbiakban.
1990-ben jelent meg a Dances of Death (and other Walking Shadows) album, melynek elkészítése előtt Wolfgang Borgmann elhagyta az együttest. Helyére az amerikai Doug Lee érkezett, aki korábban a Siren zenekarnak volt a tagja. A korongra felkerült Mogyeszt Petrovics Muszorgszkij Éj a kopár hegyen című művének átdolgozása is. A megjelenést követően Jörg Michael elhagyta a zenekart, helyére a Svájcból érkezett Peter Haas került. A zenekar ekkor kezdett el koncertezni, legfőképpen Németországban és Hollandiában. 1991-ben egy koncertlemez is megjelent, mely a Live at an Exhibition címet kapta. A koncerteken Georg Syrmbos gitáros is csatlakozott az együtteshez. A következő album Kaleidoscope címmel 1992-ben jelent meg, mely tartalmazott egy Genesis feldolgozást is a Dance on a Volcano képében. 1993-ban egy Classics című albumot jelentettek meg, mely az együttes összes komolyzenei átiratát tartalmazta, kivéve a Kaleidoscope albumon szereplő Sabre Dance címűt. 1994-ben jelent meg a Visions Fugitives album, mely zeneileg elődjei irányvonalát folytatta. A korongra felkerült egy több, mint 20 perces darab is, a hat tételből álló Suite for Group and Orchestra képében.
1997-ben jelent meg a Pictures at an Exhibition című albumuk, mely teljes egészében tartalmazta Muszorgszkij művének az Egy kiállítás képeinek feldolgozását. Mivel az album teljes mértékben instrumentális zenét tartalmaz, Doug Lee nem hallható a korongon. A Pictures at an Exhibition album rögzítése Hubert számára annyira megterhelő volt, hogy 1997-ben úgy döntött, hogy egy ideig szünetelteti zenekarát.
Aktivizálódás (2007-napjainkig)
1997 és 2007 között a Mekong Delta nem vot aktív, ez idő alatt Hubert újra megjelentette az első hat nagylemezt. A korongok feljavított hangzásáért is Hubert felelt, melyek a basszusgitáros elmondása szerint sokkal tisztább megszólalást kaptak, mint az eredeti korongok. A Mekong Delta eltűnése után olyan pletykák is szárnyra keltek, melyek azt állították, hogy Hubert Görögországba vagy Törökországba költözött, míg egyesek azt híresztelték, hogy meghalt a basszusgitáros. Hubert 2005-ben a svéd Theory In Practice gitárosával Peter Lake-kel kezdett el dolgozni. Eleinte a korábbi dobos Peter Haas is csatlakozott az együtteshez, de ő nem maradt sokáig, így hamarosan ismét Uli Kusch lett az együttes dobosa. Leo Szpigiel énekessel lett teljes a felállás, mely rögzítette az együttes visszatérő lemezének is nevezhető Lurking Feart.
Az anyag 2007. augusztus 31-én jelent meg és nagyrészt pozitív ktitikákban részesült. A korong a korábbi lemezeken megismert progresszív és experimentális thrash metalt tartalmazott, hangsúlyos komolyzenei részekkel. A lemezre Dmitrij Dmitrijevics Sosztakovics tizedik szimfóniája is felkerült. 2007-ben egy DVD is megjelent Live in Frankfurt 1991 címmel, mely nagyrészt negatív kritikákban részesült, elsősorban a filmfelvétel gyenge minősége miatt. Utolsó albumuk 2010. június 22-én jelent meg Wanderer on the Edge of Time címmel, ismét új zenekari tagokkal. Hubert mellett Martin Lemar énekelt, Alex Landenburg dobolt, valamint Benedikt Zimniak és Erik Adam H. Grösch gitároztak.
