A majsi szerb templom - akárcsak az országszerte megtalálható orthodox templomok túlnyomó része - barokk stílusban került megépítésre. Ezen épületeknek többnyire csak a belső kiképzésük az, ami sajátosan orthodox, otthonos hangulatot kelt. A templomot az ősi hagyományok szerint K-Ny-i tájolásban építették meg - úgy, hogy annak oltára esik Kelet felé - a község központjában. Lévén, hogy eredetileg is kisebb közösség igényeit volt hivatva kiszolgálni, alapterülete meglehetősen kicsinek mondható. A ma is szilárdan álló szent Paraszkéva templom a XVII. század végén, vagy a XVIII. század elején került megépítésre. Az bizonyos, hogy már 1721-ben állt, amit Bohus Imre pécsi kanonok és püspöki helynök egyházlátogatási feljegyzése igazol. A kutatások arra utalnak, hogy templomunkat 1781-ben jelentősen átépítették.

Ismereteink szerint a templomhajó és az oltár egy időben, a torony pedig később épült. Ezt követte a boltozat elkészítése. 1984-ben, a műemlékké nyilvánítás előtti kutatómunkával során feltárták, hogy a templomon nagyobb javításokat végeztek az 1859-es, az 1882-es és az 1896-os években. Kissé távolabbról szemlélve a templomot meglepően szép látvány tárul elénk. Már felületes megfigyelés esetén is feltűnik az épület tömegének arányos kialakítása. Megjelenése, szerény méretei ellenére is a régió egyik legimpozánsabb műemlékévé teszi a templomot. Jobban szemügyre véve, pedig azonnal feltűnik szokatlan módon kivitelezett, impozáns toronysapkája.