По легенде, эта икона была принесена в XIII веке в Кострому самим "святым воином" Федором Стратилатом и найдена на дереве в лесу костромским князем Василием Ярославичем, поехавшим на охоту.
Икона "Богоматерь Федоровская" была написана, вероятно, около 1239 года по распоряжению отца Василия Ярославича - великого владимирского князя Ярослава Всеволодовича. В 1239 году Ярослав Всеволодович, став великим князем владимирским после смерти своего брата Юрия, приехал на великое княжение в великий Владимир, разоренный татарами Батыя. Во время разгрома Владимира татары не пощадили и великокняжескую святыню - знаменитую византийскую икону "Богоматерь Владимирская" XII века, хранящуюся ныне в Государственной Третьяковской галерее. Они, по словам летописца, "...святую Богородицу разграбиша, чудную икону одраша, украшену золотом и серебром и каменеем драгым". Сдирая драгоценный оклад, татары сильно испортили древнюю живопись прославленного памятника. Одним из первых актов великокняжеской деятельности Ярослава Всеволодовича стала реставрация этой иконы. Но, очевидно, восстановить утраченную живопись иконы совсем близко к подлинной живописи греческого мастера было трудно. Поэтому Ярослав Всеволодович заказал для себя мастеру-иконописцу копию с "чудотворной Владимирской". Копия получила название "Федоровской" по крещеному имени Ярослава Всеволодовича, родившегося в день Федора Стратилата. Вероятно, по желанию Ярослава Всеволодовича, долго княжившего в Новгороде, на обороте новой иконы было написано изображение любимой новгородцами Параскевы Пятницы. Любопытно, что узор на плаще Параскевы по рисунку близок орнаменту на оправе знаменитого шлема Ярослава Всеволодовича, хранящегося в оружейной палате Московского Кремля.
Икона Ярослава Всеволодовича, по-видимому, была привезена в Кострому Василием Ярославичем после его возведения на великое владимирское княжение. Принесением иконы Василий Ярославич словно бы утверждал значение своей удельной Костромы как столицы Владимирского княжества. Имеется известие древних источников о том, что в 1272 году Василий Ярославич брал икону "Федоровской" на битву с татарами, подобно Андрею Боголюбскому, выносившему перед войском на поле боя икону "Владимирской", копией с которой, как говорилось выше, была "Федоровская".
С "Федоровской" приходила депутация бояр упрашивать Михаила Романова принять царский венец, ею нового царя благославляли на царство. По велению Михаила Романова, в 1636 году была проведена реставрация "Федоровской", царь заказал богатый оклад на икону, жертвовал к иконе ежегодно большие суммы денег. В XVII веке почитали "Федоровскую" во всех городах России. Появились многочисленные копии - списки с прославленной костромской иконы XIII века, им стали посвящать новые храмы, стены интерьеров которых расписывали изображениями сцен из истории древней иконы. Широкое распространение со второй половины XVII века получили иконы "Федоровской" с клеймами, в которых иллюстрировались события из истории образа. В 1670 году, по заказу иеродиакона Ипатьевского монастыря Логина, было написано "Слово о чудесах Федоровской".
В 1919 году икону Богоматери Федоровской как одно из древнейших произведений древнерусской иконописи привезли в Москву на реставрацию. Живопись ее раскрыли от многих слоев поздних записей. Сохранность красочного слоя XIII века оказалась очень плохой: на древней доске уцелели лишь незначительные фрагменты авторской живописи и рисунка фигур. Но и по этим остаткам можно судить о былом великолепии памятника. На лицевой стороне иконы находилось изображение Богоматери с младенцем. Мария была одета в темно-коричневый мафорий, украшенный золотой каймой с красными рубинами и двумя запонами в виде крупных ромбов, унизанных по краям жемчужными прядами. Головы Марии и младенца окружали белые нимбы, силуэты фигур четко выделялись на серебряном фоне.