Всё началось с того, что в 1993 году под руководством духовенства Острогожского благочиния приступили к расчистке древних Костомаровских пещер. А в 1997 году монастырь официально вернули Русской православной церкви и возобновили как женский. К этому моменту пещерный комплекс был в запустении, и его пришлось полностью восстанавливать.
Именно в ходе этого возрождения и возникла потребность в дополнительном храме. Дело в особенностях местности: в пещерах постоянно держится одна и та же температура и влажность. Летом службы удобно проводить в восстановленных подземных храмах (например, в Спасском или в храме преподобного Серафима Саровского), а зимой из-за сырости и холода комфортнее служить в наземном помещении. Поэтому и решили построить отдельный наземный храм. Его и возвели к 2000 году, освятив в честь иконы Божией Матери «Взыскание погибших». С тех пор сложилась практика: летом основные службы проходят в пещерных храмах, а зимой — в этом наземном.
Есть и ещё одна важная деталь. В наземном храме «Взыскание погибших» после реставрации в 2012 году разместили чтимую икону Божией Матери «Благодатное Небо», которую в обители называют Костомаровской.