Црквата „Св. Константин и Елена“, попозната како Влашка црква, била изградена од страна на влашката популација на Битола и се наоѓала на местото на денешен хотел „Епинал“. Храмот бил подигнат во 1903 година, како симбол на влашката национална преродба.
Црквата била изградена „тајно“, односно таа била градена како семеен дом, со цел градбата да не падне во рацете на османлиските власти или во рацете на Грчката патријаршија. Исто така, цели две години, во црквата богослужба се вршело скришно и само навечер. Дури во 1905 година Власите добиле дозвола легално да ја вршат службата на влашки јазик.
Црквата „Св. Константин и Елена“ била изградена со приземје, еден кат и визбени простории. Приземјето било составено од нартекс и наос. Подоцна, кога влашката црква се ослободила од Грчката патријаршија и кога нејзините права биле признати од османлиските власти, била подигната и трикатна камбанарија. Таа се наоѓала на десната страна од нартексот. Нејзината камбана почнала да чука од 1908 година.
Во внатрешноста на црквата немало фрески, но таа имала свој иконостас. Престолните икони биле изработени од Константин Шкодреано, познат битолски сликар во тоа време. Најстарите икони во црквата потекнувале од 1896 година.
Влашката Црква била многу оштетена за време на Првата светска војна. По нејзиното завршување, објектот бил реновиран и истиот успеал да ја преживее Втората светска војна.
Во 1969 година Влашката Црква заедно со хотелот „Централ“, кој се наоѓал до неа, биле срушени поради изградба на денешниот хотел „Епинал“. Истата година била подигната нова Влашка црква, која до денес се наоѓа во месноста наречена Стара Болница, на улица „Стив Наумов“ бр. 30. Денешната Влашка црква е копија на старата, а најголемата разлика меѓу двете е тоа што кај новата, камбанаријата се наоѓа на левата страна на нартексот. Реликвиите и другиот црковен материјал, од стариот биле преместени во новиот објект.
Влашката црква отсекогаш била во сопственост на Комуната на Власите од Битола. Меѓутоа, во 2016 година, објектот заедно со имотот на црквата, преку ноќ беа одземени од Преспанско-пелагониската епархија на МПЦ, без да биде известено битолското влашко население.