The first wooden church in Gaj was built in the 13th century. According to the tradition, in 1277 a painting of Virgin Mary was supposed to be transferred there. The temple of the Blessed Virgin Mary was also mentioned by Jan Długosz in Liber beneficionum.
The visitation records of 1598, 1610 and 1617 describes the church as wooden church with a wooden sacristy and painted beam ceiling. In the inside, there were three brick altars, pulpit on the right side, crucifix on chancel arch and wooden baptismal font.
The present brick church was built in 1626. In 1636 it was consecrated by bishop Tomasz Oborski. The visitation records of 1644 mentioned that the initiator of the construction was the then parish priest Mateusz Solecki. He transferred the miraculous painting to a new church and established the Brotherhood of the Perpetual Rosary (1644). The church was described as a brick church, with a new wooden bell tower, in which two bells hanged. There were three brick altars and a stone baptismal font inside.
The documents from the years 1703-1704 mention also choir-stalls, pulpit and an organ loft with a seven-tone organ. The bell tower was new, erected by the then parish priest Jan Broniewski. There were four altars inside the temple. The high altar of the Assumption (with the image of Virgin Mary), the altar of Our Lady of the Rosary (next to a chancel arch) and the altar of St. Anne and Martyred Christ (Misericordia Domini). A new high altar was built in 1712 and rosary reredos in 1718. The visitation records of 1729 described the baptismal font of black marble, altars - the high altar of Virgin Mary, new reredos of Our Lady of the Rosary, St. Michael and the Entombment of Christ. In the chancel, on the sides of the main reredoses, there were two small altars with the processional representations (procession floats?) and choir-stalls on the right side and pulpit on chancel arch on the left. The organ loft was made of wood with a ten-tone organ, there was also a brick sacristy and the stone floor. There were two bells in the wooden tower.
In the years 1734-1735, due to efforts of father Michał Czyrnecki, a roof framework and its covering were replaced. The visitation records of 1748 mentioned that two small altars in the chancel were renovated and repainted, reredos of St. Michael and the Entombment of Christ were described as new, however the first one had already been polychromed and gilded, and the second one was still not painted. The pulpit was black and decorated with the statues of evangelists. On the chancel arch the statue of Christ Crucified hanged. The wooden organ loft had the Mysteries of the Rosary painted on the balustrade, while the organ had seven tones and was crowned with a tympanum. The wooden tower added to the church was renovated at that time.
During the ministry of the parish priest Tomasz Lesniak (1844-1871) a trench was dug around the church in order to prevent flooding. Thanks to the parish priest's efforts, a stone flooring was laid in the church. In 1866, a wooden women's gallery was pulled down and a new one, made of brick, was built in its place. In 1868, Leśniak canonically conducted the Way of the Cross . During the ministry of parish priest Józef Machalica's, five new windows were purchased for the temple, while the the loft and the organ were renovated.
His successor, Ludwik Krzemiński, ordered going through the door from the side of the church square to sacristy.
As father Wincenty Florczyk - the parish priest in the years 1889-1901 - described in 1890, the church had "uneven walls and curve-lined arch, broken in three places, separating the nave from the chancel. It has a simple ceiling made of non plastered boards, covered with a shingle roof. A modest, Romanesque ridge turret on the roof faces the sky. A wooden bell tower built without any taste touches the front of the temple while the sacristy - the northern wall of the chancel. The women's gallery built in 1866 leans against the southern side of the nave".
During his ministry, the church was extended and renovated. The works included enlarging the sacristy from the north, raising the walls of the church by one meter and covering the interior with a rib vault. In 1899 the church was extended by one span from the west, and a tower was built. A new organ loft was built in the interior at that time. In the same year, the altar finials were partially rebuilt and a reredos with crucifix was created. In 1904, two old bells were casted and placed in the tower.
On the initiative of the parish priest Jan Kanty Skwarczyński, and with financial support of Michał and Anna from Libertów, the polychrome of the church interior was made in 1912.
During World War II, the Germans took over the tower of the church to fire the Soviets. Therefore the church was destroyed by artillery missiles.
In the years 1950-1951, on the initiative of father Jan Kuś, the temple's elements that had been damaged were rebuilt. New paraments were purchased, central heating was installed, a new floor was laid and the interior was renovated. On 2 October 1951 the reconstructed tower was consecrated.
In 1955, the women's gallery was rebuilt into chapels of the Virgin Mary. In the years 1964-1970, the roof was covered with sheet metal. In 1985, a marble floor was laid in the church. A new conciliar altar had been built earlier. Also a stone portal to the chapel of Virgin Mary and new stone steps for the altars were made. In 1990, the roof, tower and gutters in the church were painted. In the years 1993-1994, a new electric heating system was installed. In the 1990s, conservation of the furnishings was carried out. In 1997, the polychrome was renovated and carpentry works were performed in the attic, near the coping. In 1999, the sacristy was renovated, a concrete underlayment was made on the floor, marble boards were laid, walls were insulated, as well as new stairs for the pulpit and furnishings were made. At the end of August that year, the nave was covered with panelling, and the porch and stairwell leading to the loft were re-painted. The renovated interior was consecrated on 9 November 1999. After that, the vestibule was covered with panelling and the new floor was laid in the loft. The stained glass windows designed by Bolesław Szpecht and made by the workshop owned by Zbigniew Gustab were installed in the church. In 2000, another stained glass windows were ordered for the Chapel of Virgin Mary.
The first wooden temple in Gaj was built in the 18th century. The brick church with a wooden belfry was built in 1926, upon the initiative of the parish priest of the time, Mateusz Solecki. In 1866, the wooden women's gallery was pulled down and a new one, made of brick, was built in its place. During Wincenty Florczyk's ministration years (1889 - 1901), the church was extended and renovated. The works included enlarging the sacristy from the north, raising the walls of the church by one meter and covering the interior with a cross-ribbed vault. In 1899 the church was extended by one span from the west, and a tower was built. In 1912, a polychrome was made in the interior of the church. In 1950-1951, on the initiative of father Jan Kuś, a part of the church, including the church tower which was destroyed during World War II, was rebuilt. In 1955, the women's gallery was rebuilt into chapels of the Virgin Mary. The original and basic body of the church was built in the 17th century, although its style was obliterated by later reconstructions, which gave the church neo-romanesque and neo-gothic features.
Paulina Kluz, "The Church of Virgin Mary ", [in:] "The Sacred Lesser Poland Heritage", 2023, source: https://sdm.upjp2.edu.pl/en/works/the-church-of-virgin-mary