Barwy RSC Anderlecht mają niezwykły rodowód. Fiolet i biel dały klubowi przydomek Paars-wit (Mauve et Blanc), a według jednej z wersji pochodzą z parady kwiatów w gminie Anderlecht, podczas której późniejsza królowa Elżbieta jechała powozem ozdobionym fioletowymi i białymi orchideami. Fiolet jest też barwą belgijskiej monarchii. Klub założyło 27 maja 1908 roku w kawiarni Concordia przy Rue d'Aumale w Brukseli kilkunastu miłośników futbolu, pod nazwą Sporting Club Anderlechtois, a pierwszy mecz wygrał 11:8 z Institut Saint-Georges. W 1933 roku, w 25. rocznicę powstania, klub otrzymał tytuł królewski i do nazwy dodano „Royal”.
Początki w najwyższej klasie były burzliwe. Anderlecht awansował do niej po raz pierwszy w 1921 roku, ale w latach 1923, 1926, 1928 i 1931 spadał z ligi, a po każdym spadku wracał. Rywale z Brukseli, Union Saint-Gilloise i Daring, nazywali go złośliwie „klubem-windą”. Od sezonu 1935/36 klub gra w elicie nieprzerwanie. Od 1917 roku jego domem jest Park Astrid, gdzie zbudowano stadion nazwany Stade Emile Versé na cześć pierwszego wielkiego mecenasa klubu, przemysłowca Emile'a Versé. Obiekt całkowicie przebudowano w 1983 roku i nadano mu imię Constanta Vanden Stocka, prezesa klubu w latach 1971–1996. Dziś mieści 22,5 tysiąca widzów, choć pierwotnie miał ich 40 tysięcy.
Pierwsze mistrzostwo Anderlecht zdobył w sezonie 1946/47, dzięki bramkom napastnika Jefa Mermansa, sprowadzonego w 1942 roku za rekordowe wówczas 125 tysięcy franków. Mermans jest do dziś najlepszym strzelcem w historii klubu (367 goli w 399 meczach). Kolejne tytuły przychodziły w latach 1949–1956, a także w sezonach 1958/59 i 1961/62. W latach 1963/64–1967/68 klub wywalczył pięć mistrzostw z rzędu, co nadal jest rekordem belgijskiej ligi; prowadzili go kolejno Pierre Sinibaldi i Andreas Beres. Gwiazdą zespołu był Paul Van Himst, który rozegrał w klubie 457 meczów ligowych, strzelił 233 gole i czterokrotnie (1960, 1961, 1965, 1974) zdobywał belgijskiego Złotego But.
W europejskich pucharach Anderlecht zadebiutował w pierwszej edycji Pucharu Europy (1955/56), przegrywając z węgierskim Vörösem Lobogó. Pierwszy dwumecz wygrał dopiero w sezonie 1962/63, eliminując Real Madryt po remisie 3:3 w Hiszpanii i zwycięstwie 1:0 u siebie. Największe sukcesy przyszły w latach 70. i 80. W 1976 roku w Brukseli klub pokonał West Ham United 4:2 w finale Pucharu Zdobywców Pucharów (po dwa gole strzelili François Van Der Elst i Rob Rensenbrink), rok później przegrał finał z Hamburgerem SV 0:2, a w 1978 roku wygrał z Austrią Wiedeń 4:0 w Paryżu. Triumfy te dały mu dwa Superpuchary Europy: w 1976 roku z Bayernem Monachium (1:2 na wyjeździe, 4:1 u siebie) i w 1978 roku z Liverpoolem (4:3 w dwumeczu). W 1983 roku, pod wodzą trenera Paula Van Himsta, Anderlecht zdobył Puchar UEFA, pokonując w finale Benfikę 2:1 w dwumeczu. Rensenbrink uznawany jest za najlepszego piłkarza klubu XX wieku. Łącznie to pięć europejskich trofeów, najwięcej w historii belgijskiego futbolu. Klub przegrywał też finały: Pucharu Miast Targowych (1970, z Arsenalem), Pucharu UEFA (1984, z Tottenhamem) i Pucharu Zdobywców Pucharów (1990, z Sampdorią).
Po 2000 roku Anderlecht kontynuował krajową dominację: w sezonie 2006/07 miał na koncie 29 mistrzostw, 30. zdobył w 2009/10, a 31. w 2011/12. W sezonie 2011/12 jako pierwszy belgijski klub zakończył fazę grupową europejskich pucharów z kompletem punktów (Liga Europy). Ostatnie, 34. mistrzostwo wywalczył w sezonie 2016/17, z młodymi graczami takimi jak Youri Tielemans i Leander Dendoncker, a w tym samym sezonie odpadł w ćwierćfinale Ligi Europy z Manchesterem United po dogrywce. Akademia klubu w Neerpede wychowała m.in. Romelu Lukaku i Jérémy'ego Doku.
W 2018 roku klub przejął biznesmen Marc Coucke. Sezon 2019/20, w którym drużyna zajęła ósme miejsce, przerwał 55-letnią serię występów w europejskich pucharach. Anderlecht pozostaje jednym z trzech wielkich klubów belgijskich, obok Club Brugge i Standardu Liège, z którymi toczy najważniejsze rywalizacje. Jest też klubem z największą liczbą mistrzostw (34) i dziewięcioma Pucharami Belgii, choć od 2017 roku na kolejny tytuł musi czekać.