Historia Kościoła Matki Bożej Różańcowej w Puławach sięga roku 1880, kiedy wybudowano w mieście cerkiew prawosławną dla stacjonujących tam wtedy wojsk rosyjskich.
Po upadku Powstania Listopadowego, ze względu na mieszczący się w pałacu Czartoryskich w Puławach silny ośrodek patriotyczny wspierający powstańców, nowe władze starały się zatrzeć ślady Polski w mieście, przemianowując je na Nową Aleksandrię. Śladem panowania rosyjskiego w Puławach miała być między innymi cerkiew prawosławna mieszcząca się dziś przy ulicy Lubelskiej. Po I wojnie światowej cerkiew rosyjska została oddana pod nadzór kościoła katolickiego jako kościół garnizonowy poświęcony w 1921 roku. W dwudziestoleciu międzywojennym (od 1937 ro 1936 roku) dawną cerkiew przebudowano, przez co straciła ona cechy charakterystyczne dla budowli sakralnych prawosławia, między innymi kopuły. W trakcie II wojny światowej kościół Matki Bożej Różańcowej nie doznał większych zniszczeń, dzięki czemu przeszedł tylko niewielki remont i malowanie w 1972 roku, a także wymianę pokrycia dachu w latach 80. W czasach współczesnych do wnętrza jednonawowego budynku kościoła prowadzą trzy wejścia z przedsionkami, a nad prezbiterium, obok którego znajduje się zakrystia, można do dzisiaj oglądać jedyną pozostałość po dawnej budowli cerkiewnej – kopułę. Najcenniejszym zabytkiem we wnętrzu kościoła Matki Bożej Różańcowej jest ołtarz główny z dębowego ciemnego drewna wykonany w 1945 roku z kopią obrazu Matki Boskiej Różańcowej namalowanego przez Zofię Wójcik z Krakowa w 1975 roku. Znajdują się tutaj także obrazy przedstawiające m. in. świętego Ekspedyta, błogosławionego księdza Jerzego Popiełuszkę oraz Papieża Jana Pawła II. W związku z rozwiązaniem w Puławach jednostki wojskowej w 2001 roku, kościół przestał pełnić rolę parafii garnizonowej.