Манастирот Св. Богородица - Вељуса е изграден во средниот век, во византискиот период, на оддалеченост од 7 км западно од Струмица во с. Вељуса се наоѓа манастирската црква Света Богородица Милостива (Елеуса), посветена на празникот Воведение на Пресвета Богородица (21 ноември стар и 4 декември нов стил). Според изворно богатата историска документација зачувана за овој манастир (присутни во Светогорскиот манастир Ивирон) оваа црква го зазема едно од најзначајните места во црковната и културната историја не само во југоисточниот дел на Македонија, туку пошироко на Балканот.

Според сочуваните записи на двата архитрава кои биле однесени од бугарските власти за време на Првата Светска војна во Софискиот археолошки музеј, црквата ја подигнал на северните падини на планината Еленица на бигореста карпа монахот, а подоцна струмички епископ Мануил во 1080 год. кој дошол од Халкедонскиот манастир Св. Авксентиј од малоазијската област Витинија во Вељуса. Од споменатите извори дознаваме дека манастирот Св. Богородица Милостива (Елеуса) е изградена над некогашното село Палеокастро во Темата Струмица по кој и селото го добило денешното име.

Манастирот се споменува и во Грамотите на византискиот император Алексиј I Комнен 1085 год., во една од годините на 1091 или 1094 година оваа манастирка црква била лично посетена од византискиот император Алексеј I Комнен, кој за нејзините убавини изразил силен восхит во пишаните извори. Се споменува во Типикот за манастирот составен од основачот Мануил меѓу 1085-1100 год., неколку документи од византискиот император Мануил I Комнен со Практикот од 1152 год. и две Грамоти од Српскиот цар Стефан Душан од 1346 година дадени на Иверонскиот манастир. Со своето архитектонско обликување изворно сочувано до денес, таа ги презентира високите дострели на византиската сакрална архитектура и уметност на македонската територија во средниот век. По своето архитектонско решение црквата е единствена градба во Македонија од XI век. Однатре е крстообразна куполна градба од стеснат тип цркви. Сите три основни делови на црквата: наосот со олтарот, нартексот и јужната капела Св. Спас се надвишени со различни по димензија и височина куполи со полигонални тамбури украсени со керамопластична декорација и полихромно оживување на фасадите. Со фреско украсна изведба е на јужната фасада на црквата, во нејзиниот горен централен дел е сместена мала богато профилирана розета со запчест венец, а подолу меѓу бифората е раскошна двочленска плетеница со претстава на орнаментиран украс во форма на крст. Уметничките сликарски изрази се реализирани во фреско - техника, мозаик и вајарските во плиток релјеф на мермерните делови на иконостасот.

Живописувањето на црквата е изведено во три временски периоди и тоа: во олтарот, подкуполниот простор во наосот и ѕидовите, конхите, и капелата, 1085 год. во тремот од 1164 год. и во наосот од 19 век, со доста локални сликарски призвуци.

Фреско - ансамблот во црквата е со иконографски симболични содржини и претстави преземени од Стариот и Новиот завет: Литургиска служба на светите Архиереи со Хетимазијата (Христово жртвување) и Богородица со Исус Христос седната на трон во олтарниот простор. Во централниот куполен простор е насликан Исус Христос Вседржител, додека под него на ѕидовите од тамбурот се претставите: Пресвета Богородица Ширшаја, Св. Јован Крстител, двајца архангели, четворица пророци (езекиј, Авакум, Еремија и Давид). Во северната конха е Слегнувањето на Исус Христос во пеколот и Сретение Господне е во јужната конха. Во јужната капела Св. Спас во куполниот простор претставен е Исус Христос Емануил, на источниот ѕид Исус Христос во слава и портретот на Св. Пантелејмон на западниот ѕид.

На јужната фасада под тремот е композицијата Св. Онуфриј во пустина посетен од монахот Св. Панфнутиј и стилизиран вегитабилен мотив. Во стилско - ликовен поглед оваа сцена и мотивот се блиски на фреските во Нерези насликани во 1164 година.

Во наосот на црквата зачувана е и олтарната преграда, изведена во мермер со стилизирани растителни и геометриски мотиви изведени во плиток релјеф.

Во подниот мозаик застапени се геометриски мотиви и ги пратат основите на конхите во централниот дел од наосот, натрексот и јужната капела.

Изградбата на Вељушкиот храм е карактеристична и по многу претенциозните желби на основачот: не со димензиите, туку пред се со ликовните вредности и раскошната ризница од скапоцени уметнички творби да ги надмине сите постојни уметнички остварувања на црквите во струмичката средина.