John Jacob Astor gave three lots on West 45th Street between Seventh and Eighth Avenues, "stipulating that the Church should be free, and positively orthodox in management and working."

The first church was designed by William T. Hallett, and was dedicated on December 8, 1870, the Feast of the Conception of the Blessed Virgin Mary.

Potter was unable to officiate at the service, but his place was taken by Horatio Southgate, the Episcopal Church's former missionary bishop to the Ottoman Empire.

In 1892, the late Miss Sara L. Cooke, a member of the parish, left the church a legacy which eventually amounted to $700,000, in addition to real estate.

The chancel, at the north end of the building, was 48 feet (15 m) deep, terminating with the marble high altar moved from the former church.

In 1996-97, the interior of the church was restored by J. Lawrence Jones & Associates, resulting in vivid colors, including cobalt blue vaulting with gold stars.

A number of musicians have served as organist and music director at the parish, among them McNeil Robinson, Kyler Brown, Christopher Babcock, Robert McCormick, James Kennerley, and Simon Whalley.