1884–1989
Klub został założony w 1884 roku po odłączeniu się od lokalnej drużyny Heather Rangers. W 1890 roku Warriors przenieśli się na Ochilview Park, a następnie na Tryst Park i Goschen Park. Na początku XX wieku klub miał krótki okres sukcesów, wygrywając dwukrotnie Scottish Qualifying Cup w 1901 i 1902 roku. W latach 1902-03 klub dotarł do półfinału Pucharu Szkocji, przegrywając 1-4 u siebie z Rangersami. W sezonie 1921-22 Stenhousemuir po raz pierwszy wystąpił w rozgrywkach Scottish League Football.
W sezonie 1925-26 bramkarzowi Stenhousemuir, Joe Shorttowi, zaoferowano 50 funtów łapówki za ustawienie meczu z Broxburn, ale ten odrzucił ofertę i Warriors wygrali spotkanie 6-2. Bukmacher z Bainsford, małej wioski na obrzeżach Falkirk, został następnie uwięziony za próbę ustawienia meczu. []
W 1928 roku drewniana trybuna na Ochilview Park spłonęła w pożarze, co doprowadziło do wybudowania na jej miejscu nowej trybuny, choć z powodu błędów w planowaniu trzeba było później dobudować schody. W sezonie 1936-37 klub zanotował rekordowe zwycięstwo - wygrana 9-2 z Dundee United. Ponad dekadę później, w latach 1949-50, ćwierćfinałowy mecz Pucharu Szkocji z East Fife przyciągnął rekordową liczbę widzów - 12 500 - najwyższą w historii Ochilview Park. []. W listopadzie 1951 roku na Ochilview Park odbył się pierwszy oświetlony mecz pomiędzy dwoma szkockimi drużynami seniorów, pomiędzy Stenhousemuir i Hibernian. []
W lecie 1964 roku, Rangers FC ujawnił plan Scottish Football League, aby usunąć Warriors z ligi, wraz z czterema innymi klubami, na podstawie tego, że były one najgorzej wspierane kluby w ciągu poprzednich trzech sezonów. Cztery lata później, Stenhousemuir, wraz z Albion Rovers, Berwick Rangers, Brechin City i Stranraer, przy wsparciu wielu klubów, w tym Celtic F.C., Hamilton Academical F.C. i Airdrieonians F.C., skutecznie pokonał ten plan.
W sezonie 1972-73, Warriors pokonali Rangers 2-1 na Ibrox Stadium w Pucharze Ligi Szkockiej. Warto zauważyć, że Rangersi byli w tym czasie posiadaczami Pucharu Zdobywców Pucharów UEFA. []
1990-obecnie
W sezonie 1992-93 drużyna pozwoliła swoim rywalom Stirling Albion dzielić swój stadion Ochilview Park. W sezonie 1993-94 Warriors po raz pierwszy awansowali z najniższej ligi, dzięki utworzeniu Scottish Third Division. Połowa lat 90-tych była jednym z najbardziej udanych okresów w historii klubu; w sezonie 1994-95 Warriors pokonali St. Johnstone 4-0 i Aberdeen 2-0, oba zespoły w wyższej lidze, w drodze do ćwierćfinału Pucharu Szkocji. W sezonie 1995-96 Stenhousemuir wygrało Scottish Challenge Cup, pokonując DundeeUnited 5-4 w rzutach karnych po bezbramkowych 90 minutach i dogrywce. W procesie tym osiągnęli swój pierwszy krajowy półfinał od 1902 roku.
Stenhousemuir został zdegradowany z Scottish Second Division do Scottish Third Division po raz pierwszy w historii klubu. Jednak w następnym sezonie Stenhousemuir awansowało z powrotem do Second Division, co również było pierwszym wydarzeniem w historii klubu.
W latach 2006-07, klub ogłosił plan położenia "sztucznej" trawy na Ochilview Park. Stał się pierwszym obiektem w Wielkiej Brytanii, który przeszedł akredytację kategorii FIFA 2 Star.
Stenhousemuir awansował do Scottish Second Division po pokonaniu Cowdenbeath 5-4 w rzutach karnych po remisie 0-0 w sumie w finale play-off na koniec sezonu 2008-09. W sezonie 2010-11 klub ledwo uniknął spadku, po tym jak spędził większość sezonu w strefie spadkowej. W ostatnim dniu sezonu klub pokonał Peterhead 3-0 i awansował ponad Alloa Athletic, dzięki czemu uniknął play-offów.
W sezonie 2011/2012 sponsorem zestawu domowego jest Figure 11 Communications Ltd., zestawu wyjazdowego sponsoruje Apex Hotels, a sponsorem tylnej części zestawu jest Wright & MacLennan.
