Сказание Пролога (от 23 июня) повествует, что в царствование Юстиниана (VI в.) инок Аданской церкви (Малая Азия) Феофил служил экономом при архиерейском доме, но был оклеветан и изгнан. Не вытерпев унижения, инок возроптал, отрекся от Христа и Богородицы и заключил союз с диаволом, закрепив его "рукописанием на хартии". Впоследствии, раскаявшись в соделанном, инок затворился в храме и усердно молился перед образом Божией Матери, называя Ее "Взысканием погибших" и умоляя спасти его от вечной погибели. После долгих и отчаянных молитв Царица Небесная вняла просьбе Феофила и, возвестив о прощении грехов, вернула подписанную им хартию.
Всей православной Москве известен чудотворный образ данной иконы (сер. XVIII в.), который находится в храме Воскресения Словущего, что в Брюсовом переулке. Предание гласит, что последний ее владелец неожиданно разорился, овдовел и остался с тремя дочерьми-подростками. Находясь в крайнем унынии, он запил и был близок к самоубийству. Но из последних сил взмолился перед иконой и получил помощь. Жизнь его чудесным образом наладилась, дочери-безприданницы счастливо вышли замуж. Человек этот счел для себя недостойным иметь в своем доме чудотворный образ и передал его в церковь.
Особую милость Царица Небесная являет через Свою икону тем, кто находится в отчаянных обстоятельствах, кто чувствует себя погибающим в море грехов или на пороге духовной гибели. К чудотворному образу "Взыскание погибших" обращаются девицы, чтобы найти мужа достойного, невесты - чтобы брак был спасительным. С молениями обращаются к иконе и матери о заблудших детях; и еще о плененных и пропавших без вести.