Bart, an African-American railroad worker working on the construction of a new line in 1874, runs afoul of the bullying and racist line managers when, after the managers taunt the mainly black and Chinese workers by demanding that they sing "a good old-fashioned nigger work song", he instead leads the work crew in a rendition of "I Get A Kick Out Of You" before tricking the managers into singing "Camptown Ladies". Sent ahead with another worker to check the stability of the upcoming terrain, their handcart runs into quicksand — and when the bosses demonstrate more concern in rescuing the cart than the two workers, Bart snaps and clobbers the leader, Taggart, with a shovel. The railroad, meanwhile, will have to be diverted, and conniving State Attorney General Hedy Lamarr ("That's Hedley.") seeks to buy the land the railroad will be built on cheap so that he can profit once the trains are running. One problem; the land is already owned by the inhabitants of Rock Ridge, a small and god-fearing community made up entirely of people called Johnson — and the railroad will run right through their town.
Seeking to drive the townspeople out and buy the land up cheap, Lamarr orders Taggart and his goons to rampage through the town. The townsfolk are (mostly) made of stronger stuff, however, and petition the dimwitted, lecherous and cross-eyed state governor William J. Le Petomane to send a sheriff to restore law and order. Lamarr hits on the idea of sending a sheriff who will so offend the sensibilities of the townsfolk that they either flee the town in disgust or lynch him in rage — and conveniently Bart, awaiting execution for his earlier assault of Taggart, is right there. Lamarr convinces Le Petomane to send Bart to the town to serve as sheriff — and as expected, Bart receives a hostile welcome from the racist townsfolk, facing a lynching before he has even finished his introductory speech.
Bart is also made of stronger stuff, however, and despite the fact that he is initially greeted at gunpoint and must pose as his own hostage in order to avoid a summary lynching, attempts to serve his duties as effectively as possible. His only friend initially is the Waco Kid, a former gunslinger turned disillusioned drunk who "must have killed more men than Cecil B. DeMille", whom Bart befriends as he resides in the drunk tank. Bart also proves successful at thwarting the various attempts to destroy the town; he manages to overcome and then befriend Mongo, a brutish but surprisingly philosophical thug who is set upon the town by the railroad bosses, and also manages to seduce German seductress-for-hire Lily Von Schtupp so successfully that she ends up falling in love with him. Bart's success sees him slowly but surely win over the townsfolk, but infuriates Hedy Lamarr ("That's Hedley!"), who decides to assemble an army to destroy the town once and for all.
Bart and the Waco Kid, who has sobered up, learn of Lamarr's plans. Bart brings together the townsfolk and the railroad workers and urges them to work together to defeat Lamarr and his cronies once and for all. The two parties agree, with the townsfolk (with initial reluctance) allowing the railroad workers to settle in Rock Ridge once Lamarr has been defeated. Bart devises a brilliant scheme; together, the townsfolk and the railroad workers hastily construct a replica of Rock Ridge several miles away from the actual town, one rigged with dynamite. The resulting town is an almost exact replica, but Bart realises that the charade will not be convincing if the town does not appear to be populated. Distracting Lamarr's army with a hastily-constructed "William J. Le Petomane Toll Booth", the townsfolk construct dummies of themselves to fool Taggart and his thugs, but the dynamite charges initially do not detonate. After Taggart realises the sham, the Waco Kid manages to set off the dynamite with an exact shot, and the townsfolk and railroad workers swarm over the attackers in an ambush.
The resulting fight is so chaotic it literally destroys the Fourth Wall; the fight spills over first onto a musical being filmed on an adjacent soundstage, then the studio commissary, then in the streets surrounding the Warner Brothers studio lot. Although the townsfolk manage to drive away the invaders, Hedy Lamarr ("THAT'S HEDLEY!!!") discovers the fight and slips away, hailing a taxi to "get me off this picture!". He arrives at Grauman's Chinese Theatre to watch the "premiere" of Blazing Saddles, but has only just settled in his seat when the cinema screen shows Bart riding up outside the theatre on a white horse. Bart confronts Lamarr outside the cinema and challenges him to a duel; although Lamarr claims to be unarmed, he produces a gun as soon as Bart has discarded his. Nevertheless, Bart manages to get the upper hand and shoots Lamarr in the groin, who dies after leaving his handprints, footprints and signature in the concrete outside the cinema.
Bart and the Waco Kid go inside to watch the end of the movie. In the final scene, Bart, having righted wrongs and brought peace, justice and tolerance to Rock Ridge, decides to leave, and the townsfolk and railroad workers bid him a fond but sad farewell. Outside the city gates, he encounters the Waco Kid; the two men decide to accompany each other as they travel to "nowhere special", and although they initially embark on horseback, not far into their ride they encounter a limousine waiting for them, which drives them off into the sunset.