La strada statale 113 venne istituita nel [[1928]] con il seguente percorso: "[[Messina]] - [[Patti]] - [[Cefalù]] - [[Termini Imerese|Termini]] - [[Palermo]] - [[Sferracavallo]] - [[Alcamo]] - [[Trapani]]."<ref>[[s:L. 17 maggio 1928, n. 1094 - Istituzione dell'Azienda autonoma statale della strada|Legge 17 maggio 1928, n. 1094]]</ref>
Il tracciato venne ricavato dalla presistentepreesistente [[Strada nazionale 103 Sicilia-Periferica Sicula]], istituita nel [[1923]], il cui itinerario andava, nella parte iniziale, '' "Da Messina per il litorale settentrionale a Palermo, da Palermo per Sferracavallo - Alcamo a Trapani...'' La costruzione di una strada lungo la costa settentrionale della [[Sicilia]] ebbe inizio nel [[1838]], e seguiva la realizzazione, già iniziata tra il [[1778]] e il [[1824]] e ripresa nel [[1826]] del collegamento Messina-Palermo ''via montagne''. Il collegamento avviato nel [[1838]] seguiva il percorso ''via marine'', ed era di difficile costruzione, dal momento che dovevano essere superate larghe fiumare non ancora del tutto regimentate e taluni tratti di costa erano costituiti da promontori a strapiombo sul mare.<ref>{{cita web|url=http://www.provincia.messina.sitr.it/STRADARIO/files/assets/basic-html/page-3.html# |titolo=viabilità della Provincia Regionale di Messina|pagina=3|accesso=28 ottobre 2018}}</ref> Nel [[1844]] venne completata la strada da [[Messina]] a [[Patti]], rimanendo da realizzarsi il tratto da [[Patti]] a [[Tusa]] per arrivare fino a [[Palermo]]<ref>{{cita web|url=http://www.usfi.eu/wp-content/uploads/Marchese-Giuseppe-VM35-2006.pdf|titolo=La Sicilia nelle guide dei viaggiatori (di Giuseppe Marchese)|accesso=28 ottobre 2018}}</ref><ref name="tre">{{cita web|url=https://www.amnotizie.it/2016/03/16/il-malo-passo-di-gioiosa-storia-di-frane-e-di-una-strada-difficile/|titolo=Il malo passo di Gioiosa storia di frane e di una strada difficile|accesso=28 ottobre 2018|urlarchivio=https://web.archive.org/web/20181028225803/https://www.amnotizie.it/2016/03/16/il-malo-passo-di-gioiosa-storia-di-frane-e-di-una-strada-difficile/|dataarchivio=28 ottobre 2018|urlmorto=sì}}</ref>
Nella seconda metà del [[XX secolo]] non ha subito particolari interventi di velocizzazione, con l'eccezione di alcune varianti a beneficio dei centri abitati più rilevanti, tra cui [[Barcellona Pozzo di Gotto]], [[Partinico]] e [[Alcamo]], dal momento che la strada è stata sostituita, nella sua funzione di collegamento regionale, dalla rete autostradale realizzata a partire dagli [[anni 1970]], con assi perlopiù paralleli alla strada statale 113 ([[autostrada A20 (Italia)|autostrada Messina-Palermo]], [[circonvallazione di Palermo]], [[autostrada A29 (Italia)|autostrada Palermo-Alcamo-Trapani]]).
