The land upon which Madonna Church now stands was part of one of the first grants bordering the New Jersey Palisades. Given to Samuel Moore by British Army Major John Berry in 1726, this land remained in the Moore family's possession until 1829. As county records indicate, Jacob Riley purchased it and started construction on the chapel, which was subsequently completed by Henry James Anderson in 1854. A few years later, a rectory was erected at the rear of the church.
Reverend John Joseph Hughes, the first Archbishop of New York, appointed Father A. Cauvin pastor of the Fort Lee Mission in 1851, a position which Father Cauvin held until 1859 when he delegated his work to an assistant, Reverend Annelli. This decade saw the Catholics from Hackensack and Lodi gather weekly at Fort Lee for Holy Mass and spiritual instruction.
The most important individual in the young church's history was a layman, Henry James Anderson, whose remains lie beneath the church's floor with his wife and son. While seeing to the church's completion, Anderson, a convert to Catholicism, served as a surgeon and as professor of astronomy and mathematics at Columbia College in New York City. His energy and persistence won Madonna her first resident priest, Father Cauvin. The author of various scientific tracts, Anderson died suddenly while gathering information for one of these in Hindustan during exploration of the Himalayas, October 19, 1875.