Клуб основан в 1908 году. 2-кратный победитель Кубка обладателей кубков, победитель Кубка УЕФА 1983 г., 2-кратный победитель Суперкубка УЕФА, 30-кратный чемпион Бельгии, 9-кратный победитель Кубка Бельгии, победитель Кубка бельгийской лиги 2000 г., 9-кратный победитель Суперкубка Бельгии.
Основатели клуба «Андерлехт» пошли по стопам англичан, учреждавших в 1863 году Футбольную ассоциацию в лондонском пабе «Фримэйсон». Все вопросы, связанные с будущим бельгийским клубом, тоже решались за столом с едой и напитками, только не в пабе, а в брюссельском кафе «Конкордия». Во всяком случае, день встречи основателей в этом кафе — 27 мая 1908 года — и считается официальной датой рождения «Андерлехта».
К этому времени чемпионат страны разыгрывался в Бельгии уже больше десятка лет. Зарегистрировавшись в Королевском бельгийском союзе футбольных ассоциаций, новому клубу пришлось начинать с одного из низших дивизионов. Только в 1921 году «Андерлехт» впервые пробился в высший дивизион бельгийского футбола, но зато уже четырьмя годами раньше для клуба был построен стадион, на котором «Андерлехт» играет до сих пор. Сначала он назывался «Стадионом Эмиля Версе» — в честь бельгийского промышленника, который как раз в те годы взял клуб под свое покровительство.
Увы, даже при щедрой финансовой поддержке «Андерлехт» долго не мог добиться успехов. Клубу, как, впрочем, и всему бельгийскому футболу в те годы, мешало то, что он был любительским. Лишь много позже футбол в этой стране стал полупрофессиональным — игроки могли получать вознаграждения в клубе, при условии, что у них есть какое-то иное место работы. Полностью же профессиональным бельгийский футбол стал только в 1972 году.
После Первой мировой войны «Андерлехт» балансировал между Первым и Вторым дивизионами. В 1924 году вернулся из Второго в Первый, потом снова опустился вниз, и опять вернулся в 1935 году. Но после Второй мировой войны удивительным образом «Андерлехт» преобразился — последовал фантастический взлет клуба. Это была заслуга английского тренера Билли Гормли, в прошлом вратаря «Блэкберна».
Став чемпионом Бельгии в 1947 году, в следующем «Андерлехт» слегка отступил, пропустив на первое место «Мехелен», а затем побеждал в чемпионате три раза подряд. Потом вновь отступил на два года, чтобы затем одержать три победы кряду. В 60-е годы, начиная с сезона 1963–1964 годов, выигрывал титул чемпиона Бельгии пять раз подряд — такого в стране не добивался ни один другой клуб. В этот же период, весной 1965 года, «Андерлехт» завоевал свой первый Кубок Бельгии.
70-е годы стали для клуба в основном кубковыми — чемпионом в это десятилетие он стал лишь дважды, отступив в тень «Брюгге», но четырежды выигрывал Кубок Бельгии. Поэтому раз за разом вступал в борьбу за Кубок обладателей кубков и весной 1976 года завоевал его в первый раз, победив в финале лондонский «Вест Хэм».
Причем это была не просто победа — 5 мая 1976 года был сыгран один из самых лучших матчей за всю историю этого европейского турнира, который и сейчас помнят истинные знатоки футбола. «Андерлехт», как, впрочем, и «Вест Хэм», играл в бесстрашный, романтический футбол, забыв об осторожности и веря, что забить удастся больше, чем будет пропущено.
В составе обоих клубов-финалистов были хорошие футболисты. «Вест Хэм» мог рассчитывать на быстрых форвардов Билла Дженнингса, Пэта Холланда и, конечно, Брайана Робсона — полного тезки другого великолепного футболиста, несколькими годами позже заигравшего в клубе «Манчестер Юнайтед». В 1973 году Брайан Робсон из «Вест Хэма» стал лучшим бомбардиром английского чемпионата, забив 28 мячей.
У «Андерлехта» того времени были свои звезды — Франсуа ван дер Эльст, Людо Кук и, конечно, два великих голландца: Ари Хаан и Роб Ренсенбринк, футболисты сборной Голландии. Полузащитник Хаан как раз в сезоне 1975–1976 годов перешел в «Андерлехт» из амстердамского «Аякса», с которым уже успел три раза подряд выиграть Кубок европейских чемпионов. А Питер Роберта Ренсенбринк, которого обычно называли Робом Ренсенбринком, в 1971 году пришел в «Андерлехт» из… «Брюгге», главного соперника брюссельского клуба.
С первых же минут Ренсенбринк не раз создавал острые моменты, появляясь то на одном краю поля, то на другом и запутывая защитников соперника. Первый мяч, правда, на 28-й минуте забили лондонцы, но за минуту до конца первого тайма бельгийские футболисты отыгрались. Ренсенбринк сотворил один из своих футбольных шедевров. Перед ним был защитник, которого голландец легко обошел и вышел к воротам. Навстречу выбросились вратарь и другой защитник, и Ренсенбринк сильным ударом послал мяч над ними под перекладину. Счет сравнялся — 1:1.
Во втором тайме Ренсенбринк продолжал терзать оборону «Вест Хэма» своими финтами и неожиданными перемещениями. Прошло всего 3 минуты, и «Андерлехт» вышел вперед: Франсуа ван дер Эльст один оказался перед воротами «Вест Хэма» и перебросил мяч через вратаря. После этого инициативу перехватили лондонцы, сумевшие создать несколько очень опасных моментов, и наконец, на 68-й минуте они забили очень красивый гол. Атака «Вест Хэма» шла по левому краю, откуда последовала подача в штрафную площадку. Мяч достал добежавший до левого угла вратарской площадки Робсон; он причудливо изогнулся в прыжке и ударил головой в дальний угол. Мяч попал в штангу, а от нее отскочил в ворота.
Счет в матче снова стал ничейным — 2:2, но держался он недолго. Через пять минут Ренсенбринка, который пытался неподалеку от лицевой линии пройти сразу трех защитников, сбили с ног, и сам же голландец мастерки пробил пенальти. До конца второго тайма оставалось чуть больше 15 минут, и «Вест Хэм», чтобы отыграться, пошел вперед большими силами. Но последний мяч в этой игре снова забил не «Вест Хэм, а «Андерлехт», и атаку опять начинал Роб Ренсенбринк. Со своей половины поля он вывел вперед ван дер Эльста, перед которым были защитник и вратарь. Седьмой номер «Андерлехта» финтом обошел защитника и вышел к воротам. Вратарь «Вест Хэма» в броске пытался опередить ван дер Эльста и забрать мяч у него в ногах, но футболист «Андерлехта» обошел и его и закатил мяч в пустые ворота. Победив со счетом 4:2, «Андерлехт» впервые завоевал Кубок обладателей кубков.
Этой победой, одержанной под руководством голландского тренера Вила Корвера, началось самое великое трехлетие бельгийского клуба. В том же году его возглавил великий бельгийский тренер Раймон Гуталс, и осенью «Андерлехт» завоевал вдобавок Суперкубок УЕФА, победив мюнхенскую «Баварию». Следующей весной «Андерлехт» снова вышел в финал Кубка обладателей кубков, теперь финальный матч проходил в Амстердаме, на родине Роба Ренсенбринка, Увы, на этот раз «Андерлехт» уступил «Гамбургу» со счетом 0:2.
Но прошел еще один сезон, и 3 мая 1978 года на парижском стадионе «Парк де Пренс» бельгийский клуб во второй раз выиграл Кубок обладателей кубков, разгромив венскую «Аустрию» — 4:0. В первом тайме два мяча забил Роб Ренсенбринк, а во втором еще два Жильберт ван Бинст. А осенью брюссельский клуб во второй раз завоевал Суперкубок УЕФА, обыграв «Ливерпуль». Этим «Андерлехт» «отомстил» англичанам за «Брюгге» — ведь именно его «Ливерпуль» в тот год обыграл в финале Кубка европейских чемпионов.
Прошло еще пять лет, и весной 1983 года «Андерлехт» завоевал новый европейский трофей — Кубок УЕФА, победив по сумме двух финальных матчей португальскую «Бенфику». В это время клуб возглавлял знаменитый Поль Вам Химст, прежде сам выступавший за «Андерлехт». И как раз в том году «Стадион Эмиля Версе» был реконструирован, получив новое название — «Констант Ванден Сток», по имени другого покровителя «Андерлехта» — бельгийского пивовара-миллионера.
Но с тех пор «Андерлехт» больше не выигрывал международных трофеев, хотя по числу побед в чемпионатах родной страны с ним не может соперничать ни один бельгийский клуб. Последний раз чемпионом Бельгии «Андерлехт» стал в сезоне 2009–2010 годов.