Szesnastowieczna legenda opowiada o pewnym kupcu, który wykradł cudowny wizerunek z jednego z kościołów na wyspie Krecie. Kupiec ukrył obraz w swoim bagażu i wsiadł na okręt, który płynął na Zachód. Dzięki Bożej Opatrzności i opiece Matki Najświętszej statek ocalał pośród gwałtownej burzy morskiej i dobił szczęśliwie do poru przeznaczenia. W rok później kupiec znalazł się wraz ze skradzionym obrazem w Rzymie.

Ciężka choroba sprawiła, że musiał on szukać schronienia w domu swego przyjaciela. W godzinie śmierci wyjawił przyjacielowi sekret swojego obrazu, prosząc, by ten umieścił go w jakimś kościele. Przyjaciel przyrzekł spełnić to życzenie, ale ponieważ jego żona nie chciała pozbyć się tak pięknego wizerunku, umarł bez spełnienia obietnicy. Matka Boża objawiła się jednak jego córce, sześcioletnej dziewczynce, i wyraziła życzenie, by obraz Matki Bożej Nieustającej Pomocy został umieszczony w kościele pod wezwaniem św. Mateusza Apostoła, wznoszącym się między bazylikami Santa Maria Maggiore i św. Jana na Lateranie.

Tradycja podaje, że dziewczynka przekazała prośbę Madonny swojej matce, a ta „po wielu wątpliwościach i oporach, 27 marca 1499 roku oddała obraz zakonnikom obsługującym kościół św. Mateusza Apostoła”. W świątyni tej obraz odbierał cześć przez następnych 300 lat. Tak rozpoczął się drugi etap historii ikony i nabożeństwo Do Matki Bożej Nieustającej Pomocy zaczęło się rozszerzać po całym Rzymie.

Począwszy od 1739 roku kościół św. Mateusza i przyległy mu klasztor został powierzony opiece augustianów irlandzkich (zakonników).W 1798 r. Kościół i klasztor uległy prawie całkowitemu zniszczeniu na skutek działań wojennych. Część augustianów wyjechała, część wróciła do Irlandii, część przeprowadziła się do pobliskiego klasztoru zabierając ze sobą obraz Matki Bożej. Gdy w 1819 roku przejęli pod opiekę zbudowany nad Tybrem kościół Santa Maria Posterula zabrali też znowu obraz Madonny z kościoła św. Mateusza. Ponieważ w tym kościele czczono obraz Matki Bożej Łaskawej ikonę Matki Bożej Nieustającej Pomocy umieszczono w prywatnej kaplicy, gdzie pozostawała zaniedbana i zapomniana przez wszystkich z wyjątkiem brata Augustyna Orsetti, młodego zakonnika posługującego przedtem w kościele św. Mateusza. Jego wielkim pragnieniem było,  aby obraz ten znowu był znany i czczony, o to też bardzo się modlił. Jednak umarł nie doczekawszy się zrealizowania swego pragnienia.

W styczniu 1855 Redemptoryści, którzy w tym czasie rozszerzyli swoją działalność na Europę Zachodnią i Amerykę Północną, nabyli w Rzymie rezydencję zwaną „Villa Caserta”, celem przekształcenia jej w główny dom Zgromadzenia. Na terenie tej posiadłości znajdowały się właśnie ruiny kościoła św. Mateusza.

Redemptoryści interesowali się historią swojej nowej posiadłości i na skutek poszukiwań dowiedzieli się o istnieniu cudownego obrazu,  który przez wieki był czczony w kościele św. Mateusza. Tak się złożyło,  że do ich nowicjatu wstąpił dawny ministrant, który znał brata Augustyna Orsetti i któremu powiedział on skąd ten obraz pochodzi oraz wiedział, gdzie się obecnie znajduje. Redemptoryści zapragnęli lepiej poznać obraz i wystąpili do papieża Piusa IX z petycją, aby ikona Matki Bożej Nieustającej Pomocy została umieszczona w kościele redemptorystów wybudowanym przy Via Marulana, opodal miejsca, gdzie niegdyś znajdował się kościół św. Mateusza. Papież przychylił się do tej prośby zaznaczając : „Uczyńcie ten obraz znanym na całym świecie”. W styczniu 1866 ikona została odebrana augustianom. Obraz odrestaurowano i 26 kwietnia 1866 roku ponownie wystawiono do kultu publicznego.