להקת הפרוגרסיב נונסנס "גיליאם" עברה גילגולים רבים משנת 2000 ועד שהחלה להתקיים באופן רשמי, ב-2006. במשך כמה שנים ניסה הבסיסט נדב לזר להקים להקה שתתבסס על חומרים אינסטרומנטליים שהלחין בהשפעת פרנק זאפה, קינג קרימזון וג'נטל ג'יאנט, אך רק לאחר שראה את פרווה חמה הישראלים ב-1999 הבין שאפשר לעשות דברים כאלה גם בארץ. לאחר כמה גלגולים שלא ממש התרוממו ונסיעה ארוכה לחו"ל, שב לארץ ב-2004 וגיבש את ההרכב מחדש.

הראשון להצטרף היה הגיטריסט ארז קריאל, אותו פגש בהופעה של הזמרת האמריקאית ג'וליה אייזנברג, שהופיעה בארץ עם להקה שהוקמה במיוחד לכבוד האירוע. נדב ליווה אותה בגיטרה, וארז היה בקהל (שנתיים מאוחר יותר, כשאייזנברג תחזור להופעות נוספות בתל אביב, השניים יתחלפו בתפקידים). נוסף על קריאל, הצטרפו המתופף גיא שכטר (קרוזנשטרן ופארוחוד, Ed ועוד), הגיטריסט אורי בן צבי (סימפוזיון, איריס ועופר פורטוגלי) והקלידן אבירם שמיר. הציוות של ארז ובן צבי על הגיטרות עבד כל כך טוב, עד שגם להקת סימפוזיון בה ניגן בן צבי החליטה לצרף את ארז לשורותיה ב-2005. בן צבי עזב את גיליאם בתחילת 2006 בקול דממה דקה.

הבאים להצטרף להרכב היו נגן הקלרינט אורי מרום והמתופף אורי זליג, שהביא עמו את שותפו ללהקת Outer Movement, דורון פלורנטין כקלידן. לאחר תקופת חזרות אינטנסיבית, הלהקה התחילה להופיע במאי 2006. השם גיליאם (על שם הבמאי טרי גיליאם האהוב על חברי הלהקה) הועלה למעשה כבר באמצע 2005 אך נבחר סופית זמן קצר לפני הופעת הבכורה. ההופעות, שכללו קאברים לקלאסיקות טלוויזיוניות כמו מק'גייוור" ומבט ספורט, זכו לתגובות חיוביות וזיכו את הלהקה בסשן אירוח חי בתוכנית "אספסוניק" בקול הקמפוס.

לקראת סוף 2006 הלהקה יצאה לפגרה על מנת לעבוד על חומרים חדשים ולרענן את ההרכב. הקלידן דורון פלורנטין והמתופף אורי זליג הועזבו בנעימים מן הלהקה (נדב חבר אליהם שוב מאוחר יותר בלהקת Outer Movement, לימים הדוגמניות). את עמדת התופים תפס דב רוזן ואת הקלידים המירו בכלי נשיפה, שלקחו את ההרכב למקום ג'אזי-קלאסי יותר ופרוגרסיבי פחות. לאורך 2007 נגנים שונים הגיעו ועזבו, תהליך שהתיש את לזר וגרם לו לוותר על הלהקה כהרכב מופיע ולהתמקד בהקלטות בלבד. הלהקה ערכה הופעת הפתעה אחרונה בסוף דצמבר 2007 עם שלל נגנים אורחים - אליאב לביא (הדוגמניות) בגיטרה שניה, נועם דורמבוס (התפוחים) על סקסופון וליעד כהן (שממל) על חצוצרה - ופרשה מהופעות עד להודעה חדשה.