The parish was founded in 1889 by 50 German immigrant families from Bavaria and was named after Emperor Henry II of the Holy Roman Empire.

The first building of the church, a wooden structure, was built in 1890 on the northeast corner of Avenue D (now Broadway) and 26th Street (site of the current Bayonne Post Office).

[1] Construction of the current English Gothic style church, designed by architect Thomas Henry Poole, began in 1911, and was patterned after Durham Cathedral in England.

Peter E. Reilly on June 17, 1911 and the cornerstone was laid by Bishop O'Connor on September 15, 1912.

Covert took over the parish and immediately modernized the facility at a cost of $550,000 with an additional $150,000 for the school.

The interior of St. Henry's includes a Botticino marble main altar which was imported from Pietrasanta, Italy, a pulpit of carrara marble and the 28 foot high baldachino made of oak from the Balkans, lindenwood from Bavaria and local pine which, along with the screen behind the altar, were made in Urtijëi, Italy.