На станции Орелька, которая появилась в результате строительства железной дороги Лозовая – Полтава, первые её жители, а это были работники, обслуживающие станцию, обратились к управлению железной дороги и Собору Русской Православной Церкви с просьбой о постройке храма. И вот в 1915 г., в честь свт. Николая и погибших воинов Первой Мировой войны, он был построен и освящён. В храме была установлена мемориальная мраморная доска с выгравированными именами погибших воинов. По решению Священного Синода каждую пятницу служились заупокойные службы.
В 1938 г. храм был закрыт. Ценности храма были разграблены и спалены. Перед войной в храме устроили зернохранилище. Во время войны храм был занят под лагерь военнопленных, а позднее конюшню. После войны храм окончательно был разрушен, а камень взят на строительство хозяйственных зданий.
11 мая 1945 г. в Орельке была зарегистрирована церковная община, но храма не было, и службы отправляли в собственных домах верующих. В 1952 г. церковная община приобрела небольшое здание и оно в продолжение 40 лет служила храмом. И только в 1990 г. боголюбивым о. Николаем Рожком, при поддержке местной власти, хозяйств, прихожан, храм был построен и освящён 18 ноября того же года Митрополитом Харьковским и Богодуховским Никодимом. В сентябре 2013 года трудами настоятеля прот. Петра Марканича был установлен новый центральный купол. В 2015 году был установлен второй купол на колокольне и завершены работы по крыше храма.