Църквата се намира в източната страна на града в местността Дервен, където в миналото живеят известен брой влашки семейства и затова махалата е известна като Влашка. След присъединяването на Велешкота епархия към Българската екзархия в 1871 година, власите гъркомани остават без църква. В 1874 година се опитват да завладеят със сила „Свети Спас“, но опитът им завършва без успех и затова в 1882 година започват изграждането на своя църква „Успение Богородично“. В 1905 година при довършителните работи тук работи тайфата на Дамян Андреев от рода Рензовци-Зографовци.[1]
Петър Николов е автор на главните икони във велешката църква – Свети Георги от 1885 година, архангел Михаил на северната стена, Успение Богородично от 1885 година, Три светители от 1884 година, Иисус Христос, Йоан Кръстител, Свети Димитър и Свети Спиридон на южната врата.[2]
Църквата получава името Влашката църква и в нея богослужението се върши на гръцки език. Пръв свещеник на църквата е Димитър Бога, член на семейството Бога, от което произхожда и ктитора на църквата Михаил Чекърдак. Бога остава свещеник до 1915 година, но гръцката служба престава в 1912 г. със завладяването на града от сръбските войски. Епитропи на църквата са Коста Влаот, Онче Тодоров, Никола Призренец, Ямандия Гърбов, Георги Софиянов, Ташула Софиянов, Гьошо Делов, Димко Настев.[1]
