התזמורת נוסדה באשדוד בשנת 1994, על ידי מוטי מלכא וראש עיריית אשדוד יחיאל לסרי. מנצחה הראשון של התזמורת היה אברהם עילם-אמזלג. קודם לכן פעלה במתכונת שונה במסגרת המרכז לפיוט ולשירה שהוקם באשדוד בשנת 1988. ד"ר יחיאל לסרי ומוטי מלכא הקימו את התזמורת האנדלוסית הישראלית בשני גלגולים. ב-1988 הקימו עם סמי אלמגריבי, אליהו בן חמו ואריה אזולאי את המרכז לפיוט ושירה באשדוד; זה שימש ועדיין משמש בית הכשרה לפייטנים ולנגנים בכלים המסורתיים. ב-1994 התפצל המרכז לפיוט ושירה, והתזמורת, בגרסתה החדשה, הוקמה כגוף נפרד ממנו, בשיתוף פעולה עם ד"ר אברהם עילם-אמזלג, אמיל זריהן וישועה אזולאי. התזמורת הוקמה כתזמורת קלאסית עתירת כלי קשת, היא מונה כ-30 נגנים ומורכבת משתי קבוצות. הקבוצה הראשונה מכונה בשפת השדה "האותנטים", וכל השאר הם "התזמורת". רוב חברי "האנסמבל האותנטי" הם עולים מצפון אפריקה וילידי הארץ ממוצא מזרחי. נגן הכינור הראשי בהרכב הוא ערבי ישראלי ממג'ד אל-כרום. רוב חברי "התזמורת" הם עולים ממדינות חבר העמים או ילידי הארץ. הנגנים האותנטים מנגנים משמיעה, ואילו התזמורת מנגנת מקריאה בתווים.מייסדי התזמורת החליטו להפעיל את התזמורת במודל אותו הם מכנים "תזת השילוב", שלסרי הסביר אותה כך: "אנחנו הבנו שמה שלא יוגש באופן קלאסי – לא ייתפס כתרבות. רצינו להכניס אלמנטים של תרבות גבוהה למוזיקה המזרחית. המוזיקה המזרחית הפופולרית תופסת מקום ונכנסת ללגיטימיות הישראלית. אבל הם לא נותנים את הערך הנוסף, את הערך הקלאסי שבלעדיו אתה לא חודר לליבה התרבותית ולקנוניות של התרבות הישראלית. חשוב לנו להיכנס לחברה הישראלית – להיות חלק מהתרבות הישראלית. התפיסה שלנו הייתה שהתרבות הישראלית היא משהו חדש, והיה לנו הרושם שנוצרת כאן תרבות שהליבה שלה מערבית והשוליים מזרחים, וראינו שפער מעמדי מושפע מאוד מפער תרבותי. עובדה שהליבה התרבותית היא ליבה אשכנזית. יש קשר בין השניים, בין פער תרבותי לפער מעמדי".קיומו של דור ביניים משכיל, מודע לפערים החברתיים (מלכא ולסרי, כמו אחרים בסביבתם, מדגישים את החשיבות שהייתה להשתתפותם בתוכנית פעילי ציבור במסגרת לימודיהם באוניברסיטת בר-אילן), שלא עזב את המסגרת המקומית-דתית והמשיך לפקוד את בתי הכנסת כזירה תרבותית ופוליטית – היה המפתח להקמת התזמורת ולייצורה מחדש של תרבות יהודי מרוקו בישראל כתרבות הנהנית מיוקרה.התזמורת ראתה את עיקר הצלחתה "בבניית קהל מאזינים מנויים גדל והולך, מסור ומתמיד, מקרב בני הדור השני והשלישי לעליות הגדולות מצפון אפריקה ומהמזרח. זאת לצד הצלחה מזהירה גם במרכזי תרבות בינלאומיים. התזמורת האנדלוסית הישראלית נתנה ביטוי מחודש למוזיקה ולפיוטים היהודיים שנשתמרו בפיהם של יהודי ספרד מאות בשנים". (ציטוט מאתר התזמורת) מרבית נגני התזמורת מנגנים בכלי נגינה מערביים ולצדם נגנים המנגנים ללא תווים, אלא על פי מסורת העוברת מדור לדור. את המוזיקה מלווה שירה קולית של פייטנים וזמרים למיניהם. בפעולתה התרבותית וחינוכית קירבה התזמורת את הציבור היהודי לשורשיו התרבותיים וגישרה בין מזרח ומערב, בין עולים לוותיקים ובין יהודים למוסלמים. בשנת 2006 זכתה התזמורת בפרס ישראל למפעל חיים לשנת תשס"ו, כ-12 שנים לאחר הקמתה. בנימוקי חבר השופטים נאמר כי הפרס מוענק: "על התרומה שהרימה לחברה הישראלית בהעמדת הפיוט, השירה והמוזיקה האנדלוסית במרכז ההוויה הישראלית. הצלחתה להפוך את המוזיקה האנדלוסית כחלק מן התרבות הישראלית הנשמעת בישראל ומחוצה לה היא תרומה רבת משמעות. שירת הפיוטים והבקשות שהייתה חבויה בין כותלי בתי הכנסת הולכת ומתפשטת בתוך שכבות רחבות כאחת מצבעי התרבות הישראלית בת זמננו. ראויה לציון הדרך הייחודית שבה משלבת התזמורת עולים חדשים מצפון אפריקה ויוצאי חבר מדינות העמים". התזמורת הקליטה והוציאה לאור מספר אלבומים, בהם עם הסולנים אמיל זריהן וג'ו עמר.

ערך מורחב – תזמורת ירושלים מזרח ומערבהתזמורת החלה לפעול מחודש מרץ 2009 תחת עמותת "קרן אהבת קדומים" בעיר אשקלון בהשתתפות כ-28 נגנים ועובדים, שהיוו רוב ב"התזמורת האנדלוסית הישראלית". בתחילה היא נקראה "התזמורת האנדלוסית החדשה אשקלון". התזמורת ביצעה חזרות וקונצרטים ללא שכר, ובאותה העת פנתה למשרד התרבות על מנת שזה יכיר בה כממשיכת דרכה של "התזמורת האנדלוסית הישראלית" שפורקה, וכך תקבל תקציב מסוים מן המדינה. משרד התרבות בדק את שני הגופים שטענו להיות ממשיכיה של התזמורת הקודמת וב-28 בפברואר 2010 פרסם משרד התרבות ש"התזמורת האנדלוסית החדשה אשקלון" בניצוחו של תום כהן ובניהולו של עופר אמסלם קיבלה את הכרת המדינה כממשיכת "התזמורת האנדלוסית הישראלית" שפורקה וכמו כן קיבלה את התקציב לשנת 2009 (רטרואקטיבית). "התזמורת האנדלוסית החדשה אשקלון" שינתה אז את שמה ל"התזמורת האנדלוסית הים תיכונית אשקלון". לאחר מכן, גם התזמורת האנדלוסית הישראלית אשדוד החלה לקבל תקצוב מחודש ממשרד התרבות. החל משנת 2016 עברה התזמורת לעיר ירושלים עקב סכסוך עם עיריית אשקלון, וכתוצאה מכך התזמורת מאשקלון הפכה ל"התזמורת האנדלוסית ירושלים". בשנת 2017 שונה שם התזמורת שוב והפעם ל"תזמורת ירושלים מזרח ומערב".