Храм княгини Ольги и княжны Анастасии в Старом Осколе построен в 2008 году, считается крестильным храмом и расположен рядом с собором Александра Невского.
По благословению владыки Иоанна Белгородского и Старооскольского в 2007 году начинается строительство единственного на Белгородчине деревянного храма во имя святой равноапостольной княгини Ольги и мученицы княжны Анастасии.
25 июня 2007 года, в день памяти священномученика Онуфрия, епископа Старооскольского, был освящён закладной камень. Незадолго до освящения камень был доставлен издалека и установлен на место.
В апреле 2008 года каркас крыши над алтарем обшит деревянной черепицей, построены восьмерики под колокольню. 7 мая 2008 года на храм были водружены резные купола и кресты.
16 мая 2008 года установлен купол на звонницу. В течение весны и лета 2008 года обустраивалось внутреннее убранство храма: был установлен двухъярусный иконостас, налажено освящение и отопление.
Храм возведён из лиственницы, купола с крестами выпилены из осины. Иконостас и жертвенник изготовлены из дуба. Древесину привозили из архангельских лесов.
