1884–1989
De club werd opgericht in 1884 na een breuk met een plaatselijk team dat Heather Rangers heette. In 1890 verhuisden de Warriors naar Ochilview Park, na een periode in Tryst Park en Goschen Park. In het begin van de 20e eeuw kende de club een korte periode van succes, met het tweemaal winnen van de Schotse kwalificatiebeker in 1901 en 1902. In 1902-03 bereikte de club de halve finale van de Schotse beker, maar verloor thuis met 1-4 van Rangers. In het seizoen 1921-22 kwam Stenhousemuir voor het eerst uit in de Schotse League Football voor senioren.
In 1925-26 kreeg Stenhousemuir-doelman Joe Shortt 50 pond smeergeld aangeboden om een wedstrijd tegen Broxburn te verliezen, maar hij sloeg het aanbod af en de Warriors wonnen de wedstrijd met 6-2. Een bookmaker uit Bainsford, een klein dorp aan de rand van Falkirk, werd vervolgens gevangen gezet wegens poging tot wedstrijdvervalsing. []
In 1928 brandde de houten tribune in Ochilview Park af, waardoor er een nieuwe tribune voor in de plaats werd gebouwd, hoewel er later trappen moesten worden toegevoegd als gevolg van planningsfouten. In het seizoen 1936-37 boekte de club een recordoverwinning - een 9-2 overwinning tegen Dundee United. Meer dan tien jaar later, in 1949-50, trok een kwartfinale van de Schotse beker tegen East Fife een recordaantal toeschouwers van 12.500 - de hoogste ooit op Ochilview Park. []. In november 1951 vond de eerste verlichte wedstrijd tussen twee Schotse seniorenteams plaats op Ochilview Park, tussen Stenhousemuir en Hibernian. []
In de zomer van 1964 onthulde Rangers FC aan The Scottish Football League een plan om de Warriors uit de competitie te verwijderen, samen met vier andere clubs, op grond van het feit dat zij de slechtst gesteunde clubs waren gedurende de voorgaande drie seizoenen. Vier jaar later wist Stenhousemuir, samen met Albion Rovers, Berwick Rangers, Brechin City en Stranraer, met steun van een aantal clubs, waaronder Celtic F.C., Hamilton Academical F.C. en Airdrieonians F.C., dit plan met succes te verslaan.
In 1972-73 versloegen de Warriors Rangers met 2-1 in het Ibrox Stadium in de Schotse League Cup. Rangers was op dat moment de houder van de UEFA Cup Winners' Cup. []
1990-heden
In 1992-93 stond de ploeg hun rivalen Stirling Albion toe om hun stadion Ochilview Park te delen. In het seizoen 1993-94 kwamen de Warriors voor het eerst uit de onderste divisie, als gevolg van de vorming van de Schotse Derde Divisie. Het midden van de jaren '90 was een van de meest succesvolle periodes in de geschiedenis van de club; in 1994-95 versloegen ze St. Johnstone met 4-0 en Aberdeen met 2-0, beide hogere divisie tegenstanders, op weg naar de kwartfinales van de Schotse beker. In het seizoen 1995-96 won Stenhousemuir de Scottish Challenge Cup door Dundee United met 5-4 op strafschoppen te verslaan na een doelpuntloze 90 minuten en extra tijd. In het proces, het bereiken van hun eerste nationale halve finale sinds 1902.
Stenhousemuir degradeerde van de Schotse Tweede Divisie naar de Schotse Derde Divisie voor de eerste keer in de geschiedenis van de club. Het volgende seizoen won het echter weer promotie naar de Tweede Divisie, ook een primeur in haar geschiedenis.
In 2006-07 kondigde de club een plan aan om 'nep' gras aan te leggen op Ochilview Park. Het werd de eerste in het Verenigd Koninkrijk die slaagde voor de FIFA 2 Star-categorie accreditatie.
Stenhousemuir promoveerde naar de Schotse Tweede Divisie na het verslaan van Cowdenbeath met 5-4 op strafschoppen na een 0-0 gelijkspel in de play-off finale aan het einde van het seizoen 2008-09. In het seizoen 2010-11 ontliep de club ternauwernood degradatie na het grootste deel van het seizoen in de degradatiezone te hebben doorgebracht. Op de laatste dag van het seizoen versloeg de club Peterhead met 3-0 om boven Alloa Athletic te komen en zo de degradatie play-offs te ontlopen.
Voor het seizoen 2011/2012 wordt het thuistenue gesponsord door Figure 11 Communications Ltd, het uittenue wordt gesponsord door Apex Hotels, en de sponsor van de achterkant van het tenue is Wright & MacLennan.
