У старим писаним споменицима који помињу село под именом Милошево село налазимо информацију да је село имало цркву. Од када датира прва црква у Милошевцу није познато. Између 1925. и 1930. године пронађен је један камен у облику неправилног крста са кога се није могао прочитати натпис и он је послат у Народни музеј  Београду. У дворишту Марка Поповића налази се гвоздени крст који обиљежава мјесто на коме се налазила стара црква, она која је постојала прије ове данашње. Претпоставља се да је била од шепра, покривена дрветом, и да је имала неколико икона које су склањане када би наишли Турци.

Временом се осјетила потреба за већом и љепшом црквом и 1903. године почиње, а завршава 1906 године градња цркве која и данас постоји. Са каквим је одушевљењем, полетом и слогом грађена, види се по времену које је било потребно да се изгради - за 3 године у ондашњим техничким условима подигла се као кула светиња у посавској равници милошевачка црква, посвећења Светом оцу Николају Чудотворцу, и бијаше и до данашњих дана остаде друга по величини у Посавини. По предању, цркву су градила два брата, који су се презивали Милинковић,  из Сребренице, који су одмах након завршетка цркве у Сребреници дошли у Милошевац да граде цркву, те су ове двије цркве скоро идентичне. Сви становници Милошевца, без изузетка, су дали свој допринос у изградњи храма.

Храм је завршен 1906. године и освећен је у септембру од стране епископа зворничко-тузланског Григорија (Новаковића). Није познато ко је кумовао освећењу храма, али по причи црквењака Томе Патковића то је највјероватније био неко из фамилије Тадића. Први ко је службовао у новосаграђеној цркви био је милошевљанин Коста Поповић, који је и сахрањен у милошевачком гробљу. Усмено предање најстаријих становника милошевца каже да се у новосаграђеној цркви крстио Никола Патковић, а Лука Дринић се први вјенчао.

Црквена звона

Када је црква саграђена, постављена су три звона. Колика су била и гдје су израђена није познато. По казивању старијих и угледних житеља: Мике Јовановића, Мике Трифуновића и Томе Патковића, за вријеме Првог свјетског рата 1914-1915 она су скинута, два су однешена а једно је остало оштећено. То оштећено је однијето у Земун, у радњу "Васо Пантелић", гдје су изливена три нова звона, која су 1929. године постављена и до данашњег дана се оглашавају са торња цркве, позивајући вјерне на молитву. За вријеме Другог светског рата звона нису оштећена нити скидана. Звонило се ручно све до 04. јануара 1999. године када су звона електрифицирана, а радове су извели Борко Џакула и његов син Жељко, из Прњавора.

Иконостас

Црква Светог Николе у Милошевцу посједује веома лијеп и богат иконостас. Непознато је ко је радио иконостас, док је иконе на њему радио извјесни сликар Субановић, 1906. године, сазнајемо из натписа на централној икони Светог Васкрсења. Током своје историје, иконостас је више пута оштећиван и поправљан. Оштећења је претрпио током Другог свејтског рата 1945. година а највише је оштећен у току последњег, грађанскг рата 1992. године, од гранате која је пала непосредно испред сјеверних врата на цркви. Оштећењу је допринјело и вријеме јер су иконе биле на платну и незаштићене од утицаја свјетлости и топлине. Када су скупљена средства извршена је рестаурација иконостаса 1997. године. Конструкцију иконостаса је реновирао Перо Николић из Крушковог Поља, који је радио и иконостасе у црквама у Крушковом Пољу и Модричи, док је рестаурацију икона извршио академик Ацо Васиљевић, из Добоја. Поред иконостаса постоји још неколико икона које је радио сликар Субановић, или неко од његових асистента, крајем 19. вијека, а које су житељи Милошевца прилагали својоме храму.

Сат на цркви

Када је изграђена црква, постављен је сат, ручне израде,  на торањ цркве. На жељезној конструкцији сата је утиснута 1906. година. Непознато је ко га је и гдје израдио. Сат је радио све до 1941. године када је стао јер га због рата није имао ко навијати. По завршетку рата покушало се са оспособљавањем сата, али је покушај био безуспјешан. Чак су га и Аустријанци који су били заробљеници и радили на жељезничкој станици у Милошевцу, између 1947. и 1948. године, покушали оспособити, али без успјеха. Покушаји поправке су се настављали све до 1960. године када се пресатло са покушајима, јер се није могао пронаћи квар. Милошевљани су имали жељу да оспособе сат, нарочито они старији који су памтили вријеме када је он радио. Чекала се само повољна прилика. Током реновирања спољашњег дијела цркве 1998. године, искоришћене су скеле на звонику да се сат скине и започне са поправком. После 50 година, сат су волонтерски поправили милошевљани: Јово Н. Јовановић, Никица Ј. Јовановић, Петар Ј. Миљевић, Михајло С. Патковић, Гавро Т. Пандуревић, Драган Г. Пандуревић, Саво Г. Пејић и Илија Ђ. Тадић (слика лијево). У поправци сата су учествовали и Жика Раулић из Модриче, "Рафинерија уља" Модрича, "Памо" Модрича, "Ремонтранс" Модрича и "Металрад" Модрича. Сат је свечано пуштен у рад 18. априла 1999. године, на Томину недељу. Снимљена је и репортажа која је емитована на РТРС и РТВ БН. 

Парохијски дом

Парохијски дом је саграђен када и црква. Када су усташе упале у село 1945. године, палили су домове а ни парохијски дом није поштеђен страдања. Запаљен је али није сасвим изгорио, међутим сва документација и црквена архива су нестале у пламену. По завршетку рата је обновљен и остао у употреби све до 1975. године, када на парохију долази свештеник Урош Тодоровић. Стари парохијски дом је био дотрајао и оронуо, пун влаге, тако да је било тешко живјети у њему. На прољеће 1975. године, на иницијативу Марка Илишковића из Крушковог Поља, вриједног и амбициозног предсједника Црквеног Одбора, покреће се акција изградње новог парохијског дома. Стари парохијски дом се руши а свештеник Урош привремено станује код Пере Тадића, вриједног и честитог домаћина. Због недостатка новца, парохијски дом је грађен веома споро, а градио га је Јово Недић из Слатине. У међувремену Перин син Алекса долази из Ријеке са својом породицом, те се свештеник Урош са породицом сели код Гавре Т. Милинковића, који га прима као свога сина. Ту Урош остаје све до завршетка новог парохијског дома, и коначно се усељава у њега 28. новембра 1976. године, мада дом није био сасвим завршен, само су двије собе биле усељиве. По доласку на парохију свештеника Ђоке Б. Лазића, дом се у потпуности уређује и свана и изнутра, и коначно је завршен 1989. године. У току рата 1992-1995 године није претрпио знатна оштећења.

Реновирања храма

Храм је био оштећен током Другог свјетског рата 1945. године, нарочито олтар. По завршетку рата, одмах се кренуло са реновирањем. Радили су мјештани, а радовима је руководио Стојан Трифковић.

Милошевац је 1965. године захватило невријме - снажан циклон. Оштећени су многи домови а и храм, нарочито кров. Протојереј Душан Ц. Поповић је са мјештанима Милошевца поправио оштећења проузрокована невременом.

Протојереј Душан Ц. Поповић је 1970. године покренуо акцију и урађена је нова фасада на цркви.

Када се свештеник Урош Тодоровић уселио у нови парохијски дом 28. новембра 1978. године, неодложно је било одмах започети са реновирањем унутрашњости цркве, која је била и таквом стању да је било ризично ући у цркву, јер се свод цркве на неколико мјеста почео обрушавати. Новац је прикупљан добровољним прилозима грађана и на прољеће 1980. године почиње се са реновирањем унутрашњости цркве. Замјењени су и прозори и улазна (западна) врата. Радови су завшени на јесен 1980. године и владика Василије је осветио реновирану цркву.

Остало је још да се постави под у цркви, који је одувијек недостајао, јер од када је црква саграђена, бетонска плоча на којој је била само глазура је сачињавала под. Исте 1980. године је постављен мермерни.

Свештеник Урош и Црквени Одбор су били приморани да ставе пластичну ламперију на свод и зидове унутар цркве, јер је то тада било у тренду а и финансијски подношљиво. Међутим, касније се видјело да то и није било право рјешење. Припрема се акција да се скине ламперија, малтерише унутрашњост цркве и стави бетонски свод.

Доласком свештеника Ђоке Б. Лазића на парохију 1985. године наставља се са реновирањем и уређењем храма, који је у грађанском рату 1992-1995 године значајно оштећен.