First written mention of the settlement comes from 1412 when the village was offered to the Augustinian Order from nearby Brest by the Lithuanian Grand Duke Vytautas. During 16th century it the Order sold it to the Sapieha noble family from nearby Kodeń. In 1631 the Eastern Rite parish of St. Nicetas the Martyr was established, which accepted the Union of Brest of 1596 at some time during the 17th century, thus restoring communion the successor of St. Peter. Following the Partitions of the Polish-Lithuanian Commonwealth the village first fall under Austrian rule and later became a part of the semiautonomous so-called Congress Poland which saved the parish from the first waves of repressions against the Ruthenian (Belarusian and Ukrainian) Greek-Catholic Church until the brutal liquidation of the Eparchy of Kholm by the Russian Empire in 1875. Following the establishing of the Second Polish Republic in 1918, the parish in Kostomłoty, along with a number of other parishes (over 40 by 1939), returned into the Union in 1927, however maintaining a distinct Byzantine-Slavonic Rite, different from the Byzantine-Ukrainian Rite which has developed in the Ukrainian Greek Catholic Church that survived under Austrian rule in the region of Galicia. After the Soviet victory in World War II most of those parishes were forcibly closed, only a few which were located in the People's Republic of Poland, rather than the Belarusian and Ukrainian SSR directly controlled by Moscow, could survive. Due to the changing demographics those parishes were faced with a lack of Eastern Rite faithful in the 1960s and most have adopted the Latin Rite which has left the church in Kostomłoty the only Byzantine-Slavonic Rite parish in Poland and the entire region. Since 1969 the parish is under the care of the Marian Order. On 12 July 1998 relics of the Blessed Martyrs of Podlachia, who were murdered by Russian soldiers when praying outside a church confiscated by the tsarist regime in nearby Pratulin, were transferred here and the parish was named the Shrine of the Martyrs of Podlachia.