1884-1989
Clubul a fost fondat în 1884, în urma unei desprinderi de o echipă locală numită Heather Rangers. În 1890, Warriors s-a mutat la Ochilview Park, după ce a locuit în Tryst Park și Goschen Park. La începutul secolului al XX-lea, clubul a avut o scurtă perioadă de succes, câștigând de două ori Cupa de calificare scoțiană în 1901 și 1902. În 1902-03, clubul a ajuns în semifinala Cupei Scoției, pierzând 1-4 acasă cu Rangers. În sezonul 1921-22, Stenhousemuir a concurat pentru prima dată în Liga Scoțiană de fotbal de seniori.
În 1925-26, portarul lui Stenhousemuir, Joe Shortt, a primit o mită de 50 de lire sterline pentru a arunca un meci împotriva lui Broxburn, dar a refuzat oferta, iar Warriors a câștigat meciul cu 6-2. Un agent de pariuri din Bainsford, un mic sat de la periferia orașului Falkirk, a fost ulterior închis pentru tentativă de aranjare a meciurilor. []
În 1928, tribuna din lemn din Ochilview Park a ars într-un incendiu, ceea ce a dus la construirea unei tribune noi în locul ei, deși scările au trebuit adăugate ulterior din cauza unor erori de planificare. În timpul sezonului 1936-37, clubul a înregistrat o victorie record - o victorie cu 9-2 împotriva lui Dundee United. Mai mult de un deceniu mai târziu, în 1949-50, un meci din sferturile de finală ale Cupei Scoției împotriva lui East Fife a atras o mulțime record de 12.500 de spectatori - cel mai mare număr de spectatori înregistrat vreodată la Ochilview Park.[] . În noiembrie 1951, pe Ochilview Park a avut loc primul meci iluminat între două echipe scoțiene de seniori, între Stenhousemuir și Hibernian. . []
În vara anului 1964, Rangers FC a dezvăluit Ligii Scoțiene de Fotbal un plan de a elimina Warriors din campionat, împreună cu alte patru cluburi, pe motiv că au fost cele mai slab susținute cluburi în cele trei sezoane precedente. Patru ani mai târziu, Stenhousemuir, alături de Albion Rovers, Berwick Rangers, Brechin City și Stranraer, cu sprijinul mai multor cluburi, printre care Celtic F.C., Hamilton Academical F.C. și Airdrieonians F.C., au reușit să învingă acest plan.
În 1972-73, Warriors a învins-o pe Rangers cu 2-1 pe Ibrox Stadium în Cupa Ligii Scoțiene. În mod special, Rangers era deținătoarea Cupei Cupelor UEFA la acea vreme. []
1990-prezent
În 1992-93, echipa a permis rivalilor de la Stirling Albion să împartă stadionul Ochilview Park. În sezonul 1993-94, Warriors a ieșit pentru prima dată din liga inferioară, datorită formării celei de-a treia divizii scoțiene. Mijlocul anilor '90 a fost una dintre cele mai de succes perioade din istoria clubului; în 1994-95 au învins St. Johnstone cu 4-0 și Aberdeen cu 2-0, ambele adversare din liga superioară, în drumul spre sferturile de finală ale Cupei Scoției. În sezonul 1995-96, Stenhousemuir a câștigat Scottish Challenge Cup, învingând Dundee United cu 5-4 la penalty-uri, după 90 de minute și prelungiri fără goluri. În acest proces, ajungând în prima lor semifinală națională din 1902.
Stenhousemuir a retrogradat din a doua divizie scoțiană în a treia divizie scoțiană pentru prima dată în istoria clubului.[] Cu toate acestea, în sezonul următor a obținut promovarea înapoi în Second Division, tot o premieră în istoria sa.
În 2006-2007, clubul a anunțat un plan de a pune gazon "fals" pe Ochilview Park. Acesta a devenit primul din Marea Britanie care a trecut de acreditarea FIFA 2 Star category.
Stenhousemuir a promovat în a doua divizie scoțiană după ce a învins-o pe Cowdenbeath cu 5-4 la penalty-uri, după ce a remizat 0-0 la general în finala play-off-ului de la finalul sezonului 2008-09. În sezonul 2010-11, clubul a evitat la limită retrogradarea, după ce a petrecut cea mai mare parte a sezonului în zona retrogradării. În ultima zi a sezonului, clubul a învins Peterhead cu 3-0 și a trecut deasupra lui Alloa Athletic, evitând astfel play-off-ul de retrogradare.
Pentru sezonul 2011/2012, echipamentul de acasă este sponsorizat de Figure 11 Communications Ltd., echipamentul de deplasare este sponsorizat de Apex Hotels, iar sponsorul din spatele echipamentului este Wright & MacLennan.
