Budova stojící nad ulicí Rovečínskou je z olešnických kostelů nejnovější, a to i přesto, že na Moravské straně stávala v druhé polovině 16. století bratrská modlitebna. Ta po třicetileté válce osiřela, zpustla a nakonec byla zbourána. Olešničtí evangelíci se sice jistou měrou zasloužili o vydání Tolerančního patentu v roce 1781, ale budovu své modlitebny postavit v té době nedokázali, protože se jim nedostávalo především finančních prostředků. Silnější sbory v Rovečném a v Prosetíně měly i více peněz mezi svými členy, a tak postavily kostely ve svých obcích o půlstoletí dříve.

Ke stavbě kostela v Olešnici došlo až mnoho let po nich, konkrétně v roce 1860. V roce 1868 byl dostavěn. Na jeho stavbu byly peníze získávány nejen mezi věřícími v Olešnici, ale i v okolních sborech.

Přesto se jich nedostávalo, a tak zvony byly pořízeny až o 11 let později. Vedle kostela je zřízen hřbitov, který byl otevřen ještě před započetím stavby kostela. Do té doby byl společným hřbitovem katolíků i evangelíků hřbitov na Moravské straně.