Racconta una pia tradizione che San Paolo, nel corso delle sue peregrinazioni per il Mediterraneo alla volta di Roma per diffondere la Buona Novella, sarebbe approdato attorno all'anno 41 d. C. a Messina, città già allora molto fiorente dal punto di vista economico grazie al suo porto.
Qui egli, predicando la dottrina cristiana, avrebbe infiammato subito i cuori di molti messinesi e, tra essi, dei Senatori cittadini del tempo, i quali, saputo dall'Apostolo delle Genti dell'esistenza, a Gerusalemme, della Madre del Signore, decisero subito di recarvisi per chiedere la sua benedizione sulla Città.
La Madonna scrisse di suo pugno e consegnò agli ambasciatori messinesi una Lettera, in cui Ella benediceva la Città ed i suoi abitanti e si costituiva sua perpetua Protettrice. L'8 settembre del 42 d.C. la nave recò gli ambasciatori nella città dello Stretto con la Lettera di Maria, che la stessa Celeste mittente aveva arrotolato e legato con alcuni dei suoi capelli. Secondo una leggenda, Maria avrebbe scelto di essere la patrona dei messinesi e non il contrario. Questa tradizione ha contribuito molto a radicare nella città il culto mariano.
Da allora Messina divenne città mariana per eccellenza, essendo stata scelta direttamente dalla sua Patrona. La prima attestazione storica di tale epocale avvenimento è quella dello storico Flavio Lucio Destro, del II secolo. Nel Duomo è custodita la reliquia del capello della Madonna, che viene portata in processione su un artistico vascelluzzo d'argento il giorno del Corpus Domini. La Città ha sperimentato innumerevoli volte nel corso della sua storia la valevole protezione di Maria.
Si riporta il testo della lettera che la tradizione vuole sia stata scritta dalla SS. Vergine Maria:
"MARIA VERGINE, figlia di Gioachino, umilissima serva di Dio, madre di Gesù Crocifisso, della Tribù di Giuda, della stirpe di Davide, salute a tutti i Messinesi, e benedizione di Dio Padre Onnipotente. Ci consta per pubblico strumento che voi tutti con fede grande avete a noi spedito Legati, ed Ambasciatori, e confessate che il nostro Figlio generato da Dio, sia Dio, ed Uomo, e che dopo la sua resurrezione salì al celo, conoscendo voi la vita della verità per mezzo della predicazione di Paolo Apostolo eletto.
Per qual cosa benediciamo voi, e la stessa Città, della quale Noi vogliamo essere perpetua Protettrice."
Messina celebra il 3 giugno di ogni anno la Madonna della Lettera, patrona della città e patrona principale dell'Arcidiocesi, con una partecipata processione del Vascelluzzo d'argento cesellato con la statuetta argentea della Madonna, modellata da Lio Gangeri nel 1902 e la reliquia del Capello di Maria contenuta in un prezioso ostensorio (la Lettera è andata perduta in uno dei tanti incendi che devastarono il Duomo nel corso della sua travagliata storia).
