The first efforts to build a Catholic church in the area (today's Kapuściska and Wyżyny districts) date back to the interwar period.

To mitigate the decision, Primate Stefan Wyszyński had taken the initiative to support the creation of pastoral centers on Polish territory: one of them was built in Wyżyny area.

[3] The plan design was commissioned to Leopold Taraszkiewicz, a specialist of sacral construction from the Gdańsk University of Technology[4] and carried out by engineer Tadeusz Lisiewicz from Bydgoszcz.

[4] The municipal authorities designated a plot at Szpitalna street: the foundation works comprised the manual drilling of 250 15 metres (49 ft) piles into the ground, which took almost a year.

In Primate Wyszyński's decree, one can read: "This temple is to commemorate for eternity all nameless Poles who gave their lives for faith and homeland, and were not elevated to the altars."

On April 15, 1978, the cornerstone of the future church was laid: the ceremony led by the Primate of Poland Stefan Wyszyński was attended by 30,000 inhabitants.

On the same day, the site was visited by the picture Black Madonna of Częstochowa: despite a fierce opposition of the communist authorities, the procession was followed by several thousands of people.

[3] The Church of the Holy Polish Brothers Martyrs was the last place where Father Jerzy Popieluszko celebrated a mass before he was murdered by officers of the Security Service (SB).

Invited by the Pastoral Care of the Working People (Polish: Duszpasterstwa Ludzi Pracy),[8] he arrived in Bydgoszcz on October 19, 1984.

On June 7, 1999, during the Holy Mass at the airport, John Paul II referred to the symbolism represented by the invocation of the church: "This church [of the Holy Polish Brothers Martyrs] commemorates all nameless Poles who, during the history of Polish Christianity, gave their lives for Christ's Gospel and Homeland, starting with St. Wojciech [Adalbert of Prague]".He also called for the commemoration of the martyrs who gave their lives for the faith.

In response to this appeal, a year after the Pope's pilgrimage, (June 7, 2000) Henryk Muszyński, then Archbishop of Gniezno, officially elevated the church to the dignity of Sanctuary of the New Martyrs, as a way to commemorate the martyrdom of Poland.

Stefan Wyszyński, then Primate of Poland, desired personally to have the edifice dedicated to the Poles persecuted for justice; as such, he considered Bydgoszcz area to be particularly predestined for this purpose.

The reliquary, realized by the artist Robert Kaja, portrays five figures of martyrs supporting a royal crown topped with a cross.

[6] The foundations outlines draw the shape of a chalice, standing on a sacramental bread:[11] Beneath the masts rests the base of the bell tower, topped with a Greek cross.

Stained glass windows in the eastern wall quote the eight blessings on which Pope John Paul II based his teaching during his pilgrimage to his homeland in 1999.

On the inside, the carved scenes commemorate the life and mission of Blessed Father Jerzy Popieluszko (ordination, preachings, last Holy Mass in Bydgoszcz, kidnapping, torture and funeral).

[7] The four remaining entrance doors, forged by the artist Marek Rona, display Polish eagles from various periods of history: Henryk IV Probus's tombstone, Casimir III the Great's rule, Władysław II Jagiełło and Sigismund I the Old era, Stephen Báthory and John III Sobieski time, Stanisław August Poniatowski reign and the emblem of the Second Polish Republic (1919–1927).