Манастир Водоча се први пут спомиње 1018. године у повељи византијског цара Василија II, после пропасти Самуилове државе - првог Бугарског царства. Новим поводом се помиње у документу манастира Хиландара из 1376. године, када су владике Даниел и Григорије разрешили своје спорове са локалним властима око граница поседа манастира Хиландара у струмичком региону.
Данашњи спољашњи изглед цркве Водоче - манастира Светог Леонтија потврђује њен некадашњи сјај. Ипак, унутрашње уређење, које обухвата мноштво фресака, мермерни иконостас, велике престоне иконе, раскошне свете посуде, литије и драгоцене украсе, намештај и литургијску опрему су заувек нестали.
Не постоје поуздани подаци о изградњи цркве. Заправо, ради се о манастирском комплексу трију цркава Водоче из три периода градње. Најстарија црква се налази у источном делу данашње цркве и садржи само мали део преосталог олтарског простора. Друга фаза градње је обављена у првој половини 11. века, после оштећења оригиналне базилике, када је у форми уписаног крста саграђена светиња посвећена Ваведењу Богородице - уласку Богородице у храм. Из тог периода потичу једине очуване фреске - Светог Еуплуса и Светог Исарије, које су аналогне фрескама у цркви Свете Софије у Охриду и фрескама у цркви Светих Врача у Костуру - Грчка. У 12. веку је извршено проширење комплекса, када је изграђена велика крстолика црква и осликана монументалним фрескама. У другој половини 14. века је у западном делу цркве саграђена припрата и осликана фрескама. Период градње отвореног трема у јужном делу цркве није познат.
Црква манастира Водоче је позната и као место стравичног догађаја када је ослепљено 14000 војника цара Самуила, после пораза од византијског цара Василија II у бици на Беласици, по чему је насеље Водоча названо - вади очи - Водоча.[1]