Anticamente chiamata Auricella e Rocchella (dal latino medievale Roccella, piccola rocca), Roccella Mediterranea (anno 1676), quindi Roccella di Randazzo e infine Roccella Valdemone. Il nome "Valdemone" ha origine da una delle tre circoscrizioni amministrative in cui gli Arabi suddivisero la Sicilia, ossia dal Vallo di Demenna, che a sua volta discende dal latino Vallum (vallo). Il ritrovamento in territori vicini a Roccella, di monete greco-romane fa supporre la presenza di antichi insediamenti umani. A monte dell'odierno abitato, nella valle del torrente Pillera, già sin dal 1112 esisteva il cenobio di San Nicolò di Pillera (anche Pellera), elencato come uno dei trentotto monasteri dipendenti dall'Archimandrita del SS. Salvatore di Messina e del quale non si sa nulla di certo prima di tale data. È molto probabile il collegamento tra il predetto cenobio e lo sviluppo urbano dell'attuale abitato. Nel periodo normanno la popolazione si avvicina stabilizzandosi attorno al castello, che diventa un centro strategico difficilmente espugnabile. La baronia di Roccella a quell'epoca risulta costituita da sette feudi e mezzo, offerti ai Baroni come ricompensa per servizi militari resi. Regnando Federico II d'Aragona nel 1296 Damiano Spadafora risulta barone di Roccella in forza di un antico possesso e non per una nuova regia concessione. La baronia diviene marchesato con Michele Spadafora nel 1579. Lo stemma degli Spadafora, composto dal braccio destro armato di spada, tutt'oggi è raffigurato nel gonfalone comunale. Nel paese ancor oggi è viva la suddivisione in quartieri che da epoca remota hanno segnato il centro urbano: Baglittu, Tingituria, Chiazza, Santamaria, Cruci e Stratuni. Gli Spadafora (o Spatafora) ne mantennero il possesso per vari secoli (con la dominazione alterna di Ruggiero Lauria, Bonaiuto o Bonamico Mangiante, Corrado De Castellis, Famiglia Gioeni, Francesco ed Ercole Statella) fino al 1812 quando, il parlamento del Regno delle due Sicilie abolì il feudalesimo. La chiesa più importante del paese è il duomo dedicato al santo patrono Nicolò di Bari. L'edificio ubicato nella piazza principale è stato costruito nel 1625 e viene chiamato "A Matrici". L'interno è di stile romanico: tre navate con transetto, tre absidi rettangolari, dodici colonne monolitiche in pietra arenaria e con capitelli corinzi, soffitto ligneo. Nell'abside destra è conservata una pala d'altare marmorea raffigurante la Natività di Gesù, con ai lati le statue di Giovanni Battista e Nicolò di Bari. L'opera commissionata dal barone Giovanni Michele Spadafora nel 1526 ad Antonello Gagini, fu eseguita in gran parte dallo stesso, ma venne completata dal figlio Giacomo e consegnata a Roccella nell'aprile del 1540. Otto pregevoli tele di ignoti autori impreziosiscono le navate laterali della Matrice. Altra chiesa è quella dedicata a Maria dell'Udienza e verosimilmente costruita dagli Spadafora. In essa si venera una bella statua marmorea dedicata a Maria Santissima dell'Udienza che tiene in braccio Gesù Bambino. Il basamento marmoreo della statua risulta staccato e conservato in altro sito. Frontalmente sulla base è riprodotta la Dormitio Virginis, confermando l'attribuzione dell'opera ad Antonello Gagini, Nella torre campanaria di stile arabeggiante si conserva un orologio meccanico con contrappesi in pietra. Un interessante edificio religioso, probabilmente il più antico del centro urbano, è la ex chiesa di San Michele Arcangelo. All'interno si riscontrano elementi architettonici riferibili al trecento. La cripta sottostante, oggi parzialmente interrata, per lungo tempo venne usata come sepoltura per gli appartenenti alla Confraternita di San Francesco d'Assisi. Di importanza storica anche il Palazzo Spadafora, al centro del prospetto principale c'è ancora lo stemma baronale con incisa la data del 1810. Di particolare interesse il sito rupestre di Rocca Pizzicata, poco fuori il centro abitato.