У далекому 1606-му році двоє ченців-домініканців прийшли до стін Летичівської фортеці проповідувати слово Боже. Оселилися вони у двох сільських хатинках, котрі невдовзі переобладнали під монастир та під каплицю. Якось пізно вночі, коли вони молилися перед іконою Богородиці, котру принесли з собою, надзвичайне світло спалахнуло над хатинкою. Як свідчать старі рукописи, мешканцям міста здалося, що то пожежа. Та, придивившись, побачили, що вогняний стовп сходить від ікони до самого неба.
До ранку міщани стояли перед іконою на колінах. Потім староста наказав свою оселю віддати під храм. Так замок був перетворений на каплицю, в якій оселилася чудодійна ікона.
Хто написав її на полотні - невідомо. Вона не раз являла свої чудеса. Наприклад, під час нападу татар на Поділля. Тричі протягом ночі стомленому польському гетьманові Станіславу Ревері-Потоцькому, який зупинився у Летичеві, невідома жінка являлась у сні і попереджала про небезпеку. Зранку справді з’явились татари. Військо ж було готове і перемогло їх. Коли ж після бою гетьман увійшов до каплиці, щоб подякувати за перемогу, то обімлів: з ікони на нього дивилася та сама жінка, що являлась уві сні.
Гетьман наказав усьому війську здати „копитове” – пожертвування від кожного кінського копита - на будівництво храму. А будувати храм у фортеці взявся староста Ян Потоцький. Понад тридцять літ минуло, перш ніж ікона оселилась у новому храмі.
Згодом Царицю Подільську, рятуючи від набігів татар та інших ворогів, перенесли до Львова, де вона була 76 років. Лиш у 1702-му році ікона повернулась до Летичева, але не у храм, а знову у бідну хатину.
У Летичеві важко знайти родину, де б не переказували хоч одну легенду про чудодійну ікону. Є дані, що в 1777 році було організовано спеціальну комісію, яка ретельно фіксувала чудеса, що творила Летичівська Богоматір. Люди свідчили, що ікона не лише зціляла, а й оживляла з мертвих. Під своїми свідченнями вони присягались. Духовна влада визнала чудеса істинними: семеро померлих ожили, двоє сліпих прозріли, повернулись до життя п’ятеро потопельників, від недуг одужали тридцять три чоловіки.
За велінням Папи чудотворну ікону короновано. Вже у XX столітті вона перебувала у Варшаві, у Луцьку, потім знову переховувалась у Польщі.
У роки незалежності до Летичева повернулась лише копія святині. Та вже понад десяток літ люди звідусіль приходять до Летичева у день Летичівської Богородиці, вірячи у чудеса Цариці Поділля та Волині.