Roku 1443 postavil ostravský farář Řehoř na místě současného kostela kapli. Ta byla později zbořena a koncem 16. století nahrazena novou v gotickém stylu. K ní byla v 18. století přistavěna barokní loď a kaple se tak stala presbytářem nového kostela. Na kostele proběhly dvě větší opravy – v roce 1807, kdy dokonce hrozilo jeho zboření, a v roce 1913. Kostel byl od založení přifařen pod Moravskou Ostravu, od roku 1913 spadá pod Mariánské Hory.
Na hlavním oltáři stojí socha sv. Bartoloměje, patrona Nové Vsi. Vedle oltáře se nachází erb prostějovského kanovníka Františka Ondřeje z Mandorfu ze 17. století. Od 19. století zdobí oltář epitafní obraz od ostravského malíře Jiřího Milotského namalovaný roku 1639. Dva vedlejší oltáře jsou zasvěceny sv. Barboře a Matce Boží Čenstochovské.
Na hřbitově u tohoto kostela zasvěceného sv. Bartoloměji stojí památný strom, více než 300 let stará lípa.