Il documento scritto più antico a nostra disposizione in cui compare il nome di Sestola è il cosiddetto "diploma di Astolfo". Il re longobardo nell'anno 753 pone le terre a destra dello Scoltenna, tra cui appunto Sestola, sotto la giurisdizione dell'Abbazia di Nonantola, fondata l'anno precedente dal cognato Anselmo.
In questo documento, giunto a noi indirettamente e da alcuni storici considerato un "falso" (per la forma più che per il contenuto), si legge quanto segue:

"[...] Concedimus Vobis et successoribus Vestris confirmamus Monasterium S. Salvatoris situm in Fainanum cum universis legalibus eius pertinentiis, et adjacentiis, terminis et accessionibus, casalibus, alpibus, ripis, rupinis, planitiebus, cultis, incultis, aquis, aquarunque decursibus, finibus, monte et flumine, seu Sylva de Scoplano cum Castro Sextula, monte Calvo, Cervariolo, e alpe currente rivo Cerciliense, et Dardaniola fluvio percurrente. Nec non Massalizano, et Gabba cum viculis suis, idest Aquaviva, Rivofrigido, Viticiatico, Saxo Siciliano, Gricla, Variana et Porcile, cum montibus, vallibus, alpibus, sylvis, servos pro servis, liberos pro liberis [...]"

Nel X sec., mentre il dominio di Nonantola proteggeva queste zone dalle mire espansionistiche della città di Modena, i territori a sinistra dello Scoltenna cominciano a gravitare attorno alla signoria dei Canossa. Alla morte della contesa Matilde (1115) il dominio rimase di fatto nelle mani dei suoi vassalli. Anche le terre a destra dello Scoltenna, tuttavia, furono infeudate ad opera dell'abate di Nonantola. Questi vassalli che dominavano sull'area del Frignano erano detti cattani o capitanei Fregnanensis, tra i quali si distinsero i Corvoli, che in seguito presero il nome di Montecuccoli.

Dopo l'anno mille le comunità rurali cominciarono ad organizzarsi in Comuni e per Modena fu l'occasione di pretendere il giuramento di fedeltà dai nuovi consoli delle comunità locali per tentare di contrastare il dominio di Nonantola, maggiormente legata a Bologna. Anche Sestola, nonostante i giuramenti che furono infatti solo formali, risentiva ancora dell'influenza di Nonantola e probabilmente mal tollerava la poca autonomia concessa dai modenesi, infatti nel 1234 aderì con gli altri comuni del Frignano ad un patto di alleanza con la città di Bologna.
Nella seconda metà del XIII secolo tuttavia, il potere di Nonantola era assai ridimensionato e, alla fine del 1261 scese a patti con Modena rimettendo a questa gran parte delle terre su cui aveva esteso il suo dominio temporale. Così nel 1264, data l'incerta situazione politica, i Montecuccoli occuparono la Rocca di Sestola.
Nel 1276, dopo alterne fortune dei Montecuccoli e dei Montegarullo, i Comuni del Frignano si legarono al Comune di Modena. Il Comune di Modena designò Sestola capoluogo del Frignano, nonostante il parere avverso della comunità locale.

Sestola fu occupata dalle truppe pontificie nel 1521, ma alla morte di Leone X i frignanesi riuscirono nuovamente a riportare queste terre sotto la sovranità degli estensi.
Nel 1563 invece la Fortezza di Sestola venne assediata e invasa ad opera dei Tanari, in lotta con i Montecuccoli, che la devastarono, uccidendo il Governatore, il Capitano del presidio e mettendo a ferro e fuoco il paese.
E' di questo periodo la ricostruzione della Fortezza nelle forme attuali, voluta da Alfonso II su disegno di Cornelio Bentivoglio, per adattarla alle nuove esigenze militari e per l'uso delle armi da fuoco, con una prima cinta muraria a stella difeso da un fossato ed un secondo ordine di mura più esterne.
Nel 1572 furono terminate la torre dell'orologio ed il corpo di guardia, e poco più tardi la casa della Ragione.
Tra il 1600 e il 1616, temendo assalti da parte della città di Lucca venne ulteriormente fortificata. A seguito della ristrutturazione la chiesa parrocchiale all'interno del castello venne ridotta al rango di oratorio ed una nuova parrocchiale fu inaugurata nel 1619, nella posizione attuale, nel borgo ai piedi del castello.
Nel 1704 le truppe francesi la tolsero per due anni dalle mani degli Estensi, nel 1742 fu poi ceduta dal duca Francesco III al governo austro-sardo che la presidiò fino al 1749.
Nel 1797 cadde il governo Estense e la Rocca fu di nuovo occupata da un distaccamento francese: furono scalpellati gli stemmi gentilizi e cancellate le iscrizioni e nel 1801 l'ordinamento Napoleonico abolì la provincia del Frignano.
Dopo la Restaurazione il duca di Modena trasformò la Fortezza in un penitenziario rimasto in attività fino al 1866, anno in cui venne tolto il presidio militare.
Dopo l'acquisizione della Fortezza, ormai in stato di abbandono, dal Demanio da parte del Comune di Sestola (1876), nella parte alta della Rocca venne realizzato un osservatorio meteorologico (1888) ed i locali delle vecchie prigioni furono riadattati per ospitare l'Istituto Umberto I° per bambini rachitici che cominciò a considerare le doti salutari del clima di Sestola.

Il Paese di Sestola seguì le sorti del suo Castello, infatti proprio mentre finiva l'importanza ammministrativa come capoluogo del Frignano, l'apertura della via Giardini tolse all'abitato gran parte del suo traffico commerciale. Tuttavia la fama di luogo dall'ottimo clima e dall'aria salubre cominciavano a diffondersi e sul finire dell'800 cominciarono a comparire le prime ville, residenze estive dei villeggianti. L'escursionismo propagandato dalle neonate sezioni del C.A.I., lo sviluppo della forestazione ed il contemporaneo adattarsi del paese alle nuove esigenze fecero il resto ed oggi Sestola è uno dei più importanti e rinomati luoghi di villeggiatura, estiva ed invernale.