Navnet Brandstrup: Første led, 'Brand', er et gammelt dansk mandsnavn, mens 'strup' er 'torp', altså udflyttergård eller mindre udflytterby.
Folketal: Brandstrup havde, da det blev filialsogn i 1870, ca. 180 indbyggere. I dag bor her ca. 1300.
Areal: Ca. 950 ha.
Brandstrup sogn er både en gammel og en ny betegnelse. For mange hundrede år siden lå der lidt nord for den nuværende stationsby Rødkærsbro en gruppe gårde, der hed Faldborg, og her var også en kirke, Faldborg kirke, der dog blev nedrevet omkring 1655. Sognet blev kaldet Faldborg sogn eller Brandstrup sogn. Kirken var ejet af Vindum Overgaard, hvis ejer, Anders Bille, efter en synsforretning i 1653 fik tilladelse til at rive den ned på grund af ”brøstfældighed”.
Godsejeren førte en del af granitkvadrene til sit gods, hvor de blev brugt til fundering af en ny stald – den nuværende hovedbygning. Befolkningen måtte nu gå, ride eller køre helt til Vindum kirke. I århundreder derefter lå kirken hen som ruin, hvorfra egnens gårdejere hentede bygningssten og gravsten. Døbefonten har også ført en omflakkende tilværelse, indtil den i 2009 fik plads i Viborg Museums permanente udstilling. Sagnet fortæller, at Faldborgs gårde nedbrændte og blev genopført et stykke længere mod nord: Det nuværende Brandstrup.
Pastoratets oprindelige præstegård lå i den østligste ende af Brandstrup by, men biskoppen i Viborg byttede præstegården bort, og præsten blev flyttet til en gård i Vindum. På et tidspunkt klagede præsten til kongen over, at Vindum Overgaards ejer havde frataget ham gården, så han nu måtte bo i et fæstehus. Kong Frederik II forbarmede sig i 1573 over den stakkels præst og skænkede ham en gård i Brandstrup. Derved opstod den mærkværdige situation, at sognets eneste kirke lå i Vindum, mens præstegården lå – og ligger – i Brandstrup.
I 1869-70 blev der dog bygget en filialkirke i Brandstrup. Det var beboerne i Rødkærsbro, der sammen med sognepræsten og salmedigteren Julius G.V. Lassen fik ført planerne om en filialkirke i Brandstrup til en lykkelig afslutning.
Da Langå-Viborg-jernbanen åbnede i 1863, lå der kun et par små ejendomme og et par huse på stedet, hvor Rødkærsbro station blev bygget. Men kimen var lagt til en egentlig stationsby. Først kom købmandshandelen og gæstgiveriet ”Rødkjærshaab” med Jens Petersen som bestyrer. Snart købte han ejendommen og et par nabogrunde, og ganske langsomt kom der flere erhvervsdrivende til.
Stationen var dengang meget vigtig for et stort opland med dagvogne, portører og liniearbejdere, så efter 40-50 års forløb var der en hel lille by omkring landevejene og jernbanen. Rødkærsbro station blev faktisk et jernbanemæssigt trafikknudepunkt, idet der i 1912 blev etableret et jernbanespor til Kjellerup. Jernbanens store rolle illustreres af, at man til den 9 kilometer lange strækning disponerede over tre lokomotiver og 16 vogne.
I 1925 blev banen forlænget til Silkeborg – under forkortelsen SKRJ-banen. Der var også planer om at etablere en jernbanelinje til Hobro over Vejrumbro, men selvom anlægsarbejdet gik i gang, kom der aldrig til at køre tog på banen. Snart var tiden også løbet fra forbindelsen til Kjellerup og Silkeborg. Silkeborg-banen blev nedlagt i 1968.
I dag har Rødkærsbro fortsat nogle industrivirksomheder, en del håndværkere og enkelte butikker, ligesom der er jernbane- og busforbindelser til flere sider. Et par store områder er bebygget med parcelhuse, og byen nyder godt af sin beliggenhed ved hovedvejen og jernbanen og nær Viborg. Desuden er byen i højere grad blevet en enhed, efter at den stærkt trafikerede A 26 i 1998 blev ført uden om byen.