Дерев'яна церква була зведена 1648 року і проіснувала майже 250 років. Через критичний стан храму греко-католицька громада міста ухвалила рішення про будівництво нової мурованої церкви в 1896 році.

Місце вибрали ближче до головної вулиці міста, сьогодні — це вулиця А. Шептицького. Автор проекту залишився невідомим.

Дзвіниця збереглася ще з часів дерев'яної церкви, яка ведеться на обліку, як пам'ятка архітектури. У 1994 році було розпочато будівництво нової цегляної дзвіниці.

З 1944 р. церква перейшла на православний обряд.

В 1977 р. було проведено ремонт головної бані, а також позолочено кіот. Кіот у вигляді макету церкви виготовив майстер — різьбляр з м. Болехова, уродженець с. Гузієва М. Григорський.

В 1990 р. українська греко-католицька церква була реабілітована і після значного протистояння між конфесіями, приміщення церкви повернуто греко-католицькій громаді.

Пам'ятною подією в історії церкви є відправа Святої Літургії Кардиналом Мирославом Любачівським 16 квітня 1991 р., який народився в м. Долині.

До 100- річчя з дня освячення церкви проведено її ремонт. Зроблено ремонт даху. Його покрили оцинкованою бляхою імітованою під золото. Кошти на це виділив добродій Омелян Антонович. В подяку меценату п. О. Антоновичу встановили пам'ятну дошку. На ній барельєфний бронзовий портрет мецената та такі слова «Уродженець Долини Омелян Антонович благодійник цього храму» 2005 р. В ході ремонтних робіт трапилася цікава подія. В задній малій бані у сховку виявили таблицю з чорного граніту, гарно оздоблену і підготовлену до встановлення. У верхній частині викарбувано хрест (покрито золотом), нижче якого тризуб у вінку з пшеничного колосся і терну. Нижче тризуба зображено морський якір і серце. І довершує композицію напис «Борцям за волю України. Пом'яни Господи рабів твоїх за Україну життя своє поклавши». Хто і коли заховав цю таблицю, залишається невідомим. Вона зберігається в Долинському краєзнавчому музеї «Бойківщина» Тетяни і Омеляна Антоновичів.

10 серпня 2014 р. на території храму Різдва Пресвятої Богородиці встановлено погруддя главі Української Греко-Католицької церкви кардиналу Мирославу-Івану Любачівському. Погруддя виготовлено з бронзи. Автори Руслан Романишин та Василь Заляско.

Приміщення церкви це - трьохнефна, п'ятикупольна велична споруда, хрестоподібна в плані. Загальна довжина церкви 32 м, ширина 22 м, висота будівлі до хреста 32 м. Церква має четверо вхідних дверей з арочними завершеннями. Головний вхід розміщений в західному фасаді і акцентований фронтоном, що опирається на дві круглі колони. Вхідні двері дерев'яні, обшиті гарними кованими завісами, бокові окуті бляхою. Вікон є п'ятнадцять. Вони прямокутні з напівциркульними завершеннями. На бокових фасадах вікна спарені, обрамлені профільованими відкосами. Рами вікон металеві. В деяких місцях, викликаних конструктивними умовами, влаштовані круглі вікна, з металевими рамами, у вигляді шестикутної зірки або чотирипелюсткової квітки. Дах головної і бокових нав - наметовий. Бані опираються на восьмигранні барабани. В барабанах є по чотири круглих вікна (люкарни) з гарним фігурним обрамленням відкосів. Бані шоломоподібні, у верхній частині закінчуються ліхтарями. Ліхтарі перекриті грушоподібними маківками, які завершують чотирираменні хрести.

Фасади розділені вертикальними пілястрами, що завершуються півкруглими зубчиками (тригліфами). Внутрішній простір церкви видовжений з заходу на схід і розділений чотирма хрещатими в плані колонами, на три поздовжні частини - нефи. Колони вгорі з'єднані між собою підпружними арками, які разом з трикутними сферичними парусами служать основою для барабана. На колони і стіни опирається склепінчасте перекриття головної нави і бокових, що перпендикулярні до головного. Над притвором розміщені просторі хори, до яких ведуть гвинтові сходи.

Основні будівельні роботи були завершені в 1906 році і церкву в тому ж році освятив митрополит Андрей Шептицький.

Житель міста Петро Мацевич зробив велику пожертву на церкву. Він продав усе своє майно, а гроші віддав на оздоблення церкви. Вдячні долиняни встановили йому пам'ятну дошку, яка розміщена у церкві з правого боку від входу. На ній зроблений напис «В честь і пам'ять громадянина м. Долина Петра Мацевича 9/07 1857 - 7/06 1915 р., який пожертвував своє майно на прикрашення цього храму».

Забетонована мозаїчна підлога з мармурової крихти. Розмальовували стіни два майстри: Павло Ковжун з Києва і Михайло Осінчик з Сокальщини. В розписах переважають геометричні та рослинні орнаменти, які виконані в пастельних тонах блакитно-жовтого кольору.

Іконостас виготовлено в 1934 р. в майстерні п. Наконечного з Кам'янки Струмилової (тепер Кам'янка Бузька). Іконостас триярусний. Перший, нижній ярус, має три прорізи, в яких влаштовані «Царські врата», вирізьблені з дерева, і складаються з двох стулок. Врата, крім різьби, прикрашені мальовничими іконами овальної форми. Дияконські двері виготовлені теж з дерева і прикрашені різьбою. Другий ярус складається з малих ікон розміром приблизно 30 х 40 см. Третій, верхній ярус, складений з вузько-високих ікон розміром 30 х 90 см. Позолочено іконостас в 1935 р. різьбярем п. Чміль з м. Болехова. Завершення будівництва і оздоблювальних робіт громада вшанувала пам'ятною дошкою з граніту, на якій викарбувано такі слова «В 30-літній ювілей їх Високопреосвященства ексцеленції Митрополита Кир Андрея Шептицького, архіпастора і добродія українського народу, покровителя мистецтва і наук присвячується поліхромія цього храму».

Внутрішній простір церкви прикрашають і п'ять люстр. Головна, яка звисає з центральної бані, двоярусна, чотири бокові - одноярусні. Запрестольний образ «Образ Божої Матері» розташований в апсиді, виконаний в 1925 р. дочкою священика Величковського Іриною Величковською - Шухевич.

На фасаді церкви відновлено меморіальну дошку, виконану на гранітній плиті, на якій зроблений напис: «В 125 роковини з дня народження побудителя Галицької України о. Маркіяна Шашкевича. Долинська земля».