The first parish church in Bydgoszcz was erected in 1364, initially as a wooden, then stone one. In 1409, it was burnt by the Teutonic Knights, and in 1425 it was destroyed by another fire. Reconstruction began from the presbytery, which was partially preserved from the old temple. The progress of works in erecting further elements depended on the inflow of funds that the townspeople and the surrounding nobility could not fully provide. Favorable conditions for obtaining funds for the construction of the parish church were provided by the outbreak of the Thirteen Years War in 1454. During it, Bydgoszcz repeatedly hosted king Casimir Jagiellon, crowds of dignitaries and knights. In addition, in the years 1457-1475, the office of the local starost was held by Jan Kościelecki, one of the major financial tycoons of Poland at that time. In 1466, the temple was already roughly completed, and until 1502 only construction works, consisting of finishing the interior and embellishing the church, were carried out.
At the turn of the fifteenth and sixteenth century, the roofs were raised, gables were transformed, the chancel was vaulted, and on the south side of the church a tower was added. In the years 1466-1617, three side chapels were also added to the church and the gothic sacristy adjacent to the northern wall of the presbytery, was extended. In 1650, the third storey of the tower was built and it reached its present height.
The 18th century brought progressive devastation and neglect of the building. In the years 1806-1813, the church served as a warehouse, first for the needs of French and then Russian troops. Renovation work was carried out in the years 1819-1830, but three chapels that were in total ruin, were pulled down. Another thorough renovation from 1922-1925 contributed to the creation of a modernist polychrome inside. During World War II, the church was damaged, but it was rebuilt in 1945-1949.
The parish church of Saint Nicholas and Martin is an orientated, brick-built temple, built in the late gothic style. Its three-span, hall corpus, erected on the plan of a quadrilateral, divides two rows of octagonal columns. On the eastern side of the corpus there is a three-span, three-side ended chancel, with a rectangular sacristy from the north. To the main building of the church, a tower is adjoined from the south, built on a square plan. At it foot there is a porch. On the west side, an annex from the turn of the 16th and 17th centuries with an open vestibule in the ground floor, is added. The west gable of the church has a stepped form, filled with six blend zones, while the eastern one is triangular, divided by six lesenes passing into pinnacles. The chancel of the church has a net vault and aisles stellar vaults.