אנדרה היידו נולד בבודפשט בירת הונגריה בשנת 1932, לאב שניהל סניף של חנות גדולה ולאם נגנית פסנתר ובעלת סטודיו לצילום.
בנעוריו החל בלימודי מוזיקה, ובגיל 14 כתב אופרה בשם "ליאנדרה". למד באקדמיה למוזיקה ע"ש פרנץ ליסט לצד ג׳רג׳ קורטג וג'רג' ליגטי. מוריו היו סרוונסקי וסבו (הלחנה) וסגדי (פסנתר). בהדרכתו של ד"ר זולטן קודאי, שהיה מרצה בכיר באקדמיה, עסק היידו באתנומוזיקולוגיה, ולכן בילה זמן רב בקרב הצוענים ואף למד את שפתם.
בשנת 1955 זכה בפרס ראשון על יצירתו "קנטטה צוענית". בשנת 1956, לאחר המרד ההונגרי, ברח מהונגריה והיגר עם אמו לצרפת, שם למד בקונסרבטואר הלאומי של פריז אצל דריוס מיו ואוליביה מסייאן. בשנים 1960 - 1961 שהה בתוניס, שם לימד פסנתר, קומפוזיציה ותולדות המוזיקה בקונסרבטוריון ועסק בחקר מוזיקה. ושם החל להתקרב למורשת היהדות, כאשר עד לאותה עת חי חיים חילוניים לחלוטין.
בשנת 1966 עלה ארצה בעקבות המחקר המוזיקלי שעסק בו והגיע לאוניברסיטה העברית. נושא התמחותו שם היה המוזיקה הכלית של יהודי מזרח אירופה.‏ מאז 1967 הוא מרצה לקומפוזיציה באקדמיה למוזיקה בתל אביב ומשנת 1970 גם באוניברסיטת בר-אילן, שם כיהן כראש המחלקה למוזיקולוגיה. בשנת 1978 התמנה לפרופסור באוניברסיטה זו. במקביל לימד בבית הספר התיכון למדעים ולאמנויות בירושלים. במהלך עבודתו פרסם את הספר "לאן שוחים דגי הסלמון - שיחות על מוזיקה", בשיתוף עם מירה זכאי.
בשנת 1997 הוענק לו פרס ישראל למוזיקה. בשנים 2001 - 2006 יחד עם קבוצת תלמידיו מבית הספר התיכון למדעים ולאמנויות השתתף והנהיג את אנסמבל האומן ח"י. האנסמבל שקרוי על שם הסטודיו של ברחוב האומן 18 בתלפיות שבו התקיימו המפגשים המוזיקליים, התפרסם לראשונה בעקבות מופע עיבודים עכשוויים לניגוני חב"ד שנקרא "קולמוס הנפש" (עלה בבכורה בפסטיבל ישראל 2004). מופע פופולרי אחר של האנסמבל הוא "מגדל פורח באוויר" המבוסס על יצירותיו של היידו "שירי משנה", שנכתבו בשנות ה-60. המופע הועלה בפסטיבל ישראל 2007 ובפסטיבל "לילות קיץ" 2006 של הזירה הבין תחומית."התפילה המשונה של היידו היא תשובה אחת, אפשרית, מרתקת, לשאלת הזהות היהודית...." (אורי הולנדר, "הארץ", תרבות וספרות, 15.6.07)

בין תלמידיו של היידו: גדעון לבינסון שהחליפו כראש המגמה לקומפוזיציה באוניברסיטת בר-אילן, יוני רכטר, גיל שוחט, אבי ברמן, מתי קובלר, נורי יעקובי, יונתן ניב, אסנת נצר, מתן פורת, דניאל שליט, האחים יונתן רזאל ואהרן רזאל, נטע אלוני, יאיר הראל, אוריאל זוהר, רונן שפירא, משה שלגי, ועוד רבים אחרים.

נמנה עם המייסדים של האופרה הירושלמית ב-2012.