Wzniesiony w latach 1908-1909 w stylu neogotyckim. Poświęcony 3 maja 1912 roku przez biskupa Józefa Sebastiana Pelczara pod wezwaniem Matki Bożej Królowej Polski. Kościół przetrwał I i II wojnę bez poważnych zniszczeń. Gdy do Ustrzyk w 1944 roku wkroczyły wojska radzieckie, zamieniono go na magazyn zbożowy. W tym czasie zniszczeniu uległ obraz Matki Bożej Szkaplerznej w głównym ołtarzu. Po wymianie w 1951 roku odcinków przygranicznych między Polską a ZSRR (akcja H-T), Ustrzyki Dolne wróciły w granice Rzeczpospolitej. Świątynia wymagała remontu; w tym czasie katolicy rzymscy modlili się w opuszczonej cerkwi greckokatolickiej. W 1952 roku odnowiony kościół na nowo zapełnił się wiernymi i zaczął funkcjonować jako parafia pod wezwaniem Najświętszej Maryi Panny Królowej Polski. W latach dwutysięcznych, m.in. ze składek wiernych, dobudowano wysoką wieżę i poszerzono wnętrze.
