Dnešní kostel stojí na místě středověkého kostela. Zmiňován je v roce 1298, jiný údaj z farní kroniky uvádí rok 1384. Lze tedy soudit, že kostel existoval již v době, kdy újezd patřil doksanským premonstrátkám. V 16. století byl v podlaze kostela pravděpodobně umístěn náhrobník místního šlechtice J. T. Mangolta. V 17. století kostel vyhořel a při jeho přestavbě byl náhrobník zazděn do ohradní zdi na přilehlém hřbitově. Na počátku 90. let 19. století byl podle obecní kroniky kostel považován za neopravitelný a posléze zbořen. Stavbu kostela Nanebevzetí Panny Marie v současné podobě uskutečnil J. Peter z Kadaně podle plánů architekta Ludvíka Láblera v letech 1895–1896. K vysvěcení nové svatyně došlo roku 1987. Velké zásluhy na výstavbě nového kostela měl také nepochybně tehdejší farář Peter Carl Baumgärtl, který ve Velichově vykonával kněžskou funkci od konce 80. let 19. století až do roku 1912. Byl rovněž zakladatelem další stavební dominanty obce – hospicu pro nevyléčitelně nemocné. Jednolodní stavba s vysokou věží v jihozápadním průčelí a s odsazeným pravoúhlým presbytářem je vybudována ve vznosných neogotických formách. Loď je prolomena čtveřicí vysokých hrotitých oken s ušlechtilými kružbami, presbytář obsahuje na každé straně po dvojici obdobných oken. V meziokenních intervalech jsou přisazeny opěrné pilíře, v nároží presbytáře situované šikmo. Věž je prolomena mohutným vstupním portálem se štítem obsahujícím původně kraby a zakončeným vrcholovou kytkou. Nad portálem bylo otevřeno velké trojdílné okno s bohatou kružbou. K věži se na západní straně přimyká trojboká kaple zastřešená zvalbenou stříškou a z opačné východní strany těleso schodiště vedoucí do patra věže a do podkroví lodi, v přízemí hranolové a v patře přerůstající do válcové věžičky zastřešené kuželovou střechou. Horní patra velké věže jsou osvětlena úzkými střílnovými okny a v nejvyšším patře dvojicí hrotitých oken. Věž je zastřešena vysokou stanovou střechou. K severovýchodnímu koutu lodi a presbytáře je vložena obdélná sakristie osvětlená dvojicí hrotitých oken. V ose podélného průčelí sakristie je vysazen vysoký stupňovitý štít s nikou doplněnou vimperkem, ve které stojí na profilované konzole plastika korunované Panny Marie s palmovou ratolestí v rukou.