Do r. 1874 istniała tu parafia greckokatolicka. Została zlikwidowana w listopadzie tegoż roku, a na jej miejsce utworzono prawosławną, która istniała do I wojny światowej. Na terenie dzisiejszej parafii był nadto kościół unicki w Szewni – filia parafii unickiej w Potoczku. Prawdopodobnie był również parafialny kościół unicki w Wieprzcu wskazują na to miejsce dawnego unickiego cmentarza grzebalnego i relacje ustne mieszkańców. Prawosławni mieszkali na terenie dzisiejszej parafii Kosobudy jeszcze w okresie międzywojennym. W czasie II wojny światowej zamienili oni kościół w Szewni na cerkiew prawosławną. Katolicy obrządku łacińskiego należeli do początku  XX wieku do parafii Wielącza, a część wsi okolicznych również do rzymskokatolickiej parafii Krasnobród. Parafia łacińska w Kosobudach została erygowana, 26 II 1919 r., przez bpa. Mariana Fulmana. Powstała z podziału parafii Wielącza i Krasnobród. Nowa parafia Kosobudy została włączona do Dekanatu Zamość.  Od 1978 r. do Dekanatu Zamość Nowe Miasto. Od r. 1994 do Dekanatu Krasnobród.

W r. 1919 utworzono bractwo różańcowe (istniał już wtedy trzeci zakon św. Franciszka). W okresie międzywojennym wielką czcią otaczano obraz Matki Bożej, umieszczony w kościele parafialnym (MB Kosobudzka, obraz ten spłonął podczas II wojny). Rejon Kosobud był kilkakrotnie terenem walk partyzanckich: w odwet okupanci spacyfikowali Kosobudy i Wieprzec. W styczniu 1940 r. aresztowano ks. Mieczysława Karpińskiego. W lipcu tego roku aresztowano następnego administratora parafii, ks. Franciszka Kapalskiego. 6 VI 1943 r. Niemcy zabrali z kościoła około 120 mężczyzn i wywieźli do obozu na Majdanek.

Obecny kościół wybudowany w latach: 1842-1848 dla unitów, z fundacji ordynacji zamojskiej, restaurowany w listopadzie 1870 r., w r. 1874 zamieniony na cerkiew prawosławną. W posiadaniu prawosławnych do r. 1918, rekoncyliowany, 28 VII 1918 r., przez ks. Andrzeja Wadowskiego ze Szczebrzeszyna. 25 VII 1944 r. spłonął od uderzenia pocisku armatniego. Odbudowany w latach: 1944-1948, a 16 V 1948 r. konsekrowany przez bpa. Lubelskiego Stefana Wyszyńskiego (pw. św. Andrzeja Boboli). Renowacja dachu nastąpiła w latach 1948-1957.

Kościół murowany z kamienia, jednonawowy (po ostatniej odbudowie nieco zmienił wygląd: dodano jeszcze zakrystię, zlikwidowano dwie wieże, zmieniono dach, chór i wejście). W nawie sklepienie płaskie, w prezbiterium kolebkowe.

Kościół został wyposażony w marmurowy ołtarz główny, wykonany przez kamieniarzy z Kielc w r. 1945. W ołtarzu tym obrazy: 1. Matki Bożej (powojenny, miało to być odtworzenie dawnego obrazu MB Kosobudzkiej), 2. św. Andrzeja Boboli (powojenny). Po prawej stronie znajduje się drewniany ołtarz boczny. W nawie stoją ławki wykonane przez miejscowych stolarzy, chrzcielnica dębowa z r. 1948.