Kostel Všech svatých v Újezdu u Černé Hory je jednolodní stavba s prodlouženým presbytářem a apsidou, věží a sakristií. Postaven byl na počátku 13. století jako šlechtická svatyně v románském slohu, o čemž svědčí vstupní portál na jižní straně. Nejstarší dochovanou zprávou je zápis z roku 1308 o faráři Jakubu z Újezda.

V roce 1744 kostel spolu s farou a téměř celou vsí vyhořel a zůstal delší dobu v ruinách. V roce 1750 byl zhotoven zednickým mistrem Františkem Josefem Stachou z Černé Hory plán na obnovu kostela v barokním slohu. Přestože měla Újezdská farnost šest vrchností, nikdo z nich nechtěl opravu financovat.

Kostel byl v letech 1750 - 1754 obnoven díky tomu, že farář Jakub Želivský věnuje na opravu svoje úspory. Zbytek dodali farníci - nevolníci. Náklad na obnovu činil 905 zlatých, vnitřní vybavení 300 zlatých. V rozpočtu není obsažena doprava materiálu a robotnické práce. Byl odstraněn plochý strop a nahrazen valenou klenbou s výsečemi taktéž v presbytáři. Ke škodě stavby samé byly odstraněny všechny románské prvky, byl zachován pouze vstupní portál.

Věž kostela je členěna horizontálně probíhající římsou, zvonicové patro prolomeno třemi okny s půlkruhovým závěrem. Na věži byly tři zvony. Největší z nich o průměru 83 cm, přibližná váha 310 kg, je z roku 1940. Na zvonu je nápis: "Tento zvon slitý jest ke cti a slávě svatého Václava léta božího MCCCCXC". Druhý zvon měl průměr 59 cm, vážil 112 kg a byl z roku 1762. Třetí zvon měl průměr 49 cm, vážil 58 kg a byl z roku 1871. Druhý a třetí zvon byly 12. 3. 1917 rekvírovány pro válečné účely 1. světové války.

Větší vnitřní opravy, včetně nového oltáře a nové křížové cesty, byly provedeny v roce 1906 a 1908. V 90. letech 20. století proběhly další opravy, střecha byla opatřena měděnými okapovými svody a kostel byl uvnitř vymalován.

Kolem kostela byl původně oválný hřbitov, který byl v roce 1878 přestavěn do současné podoby.