In the summer of 1873, the Very Reverend Hugh Flattery established a chapel in the Old Red House, a resort hotel located on 105th Street in East Harlem, until a small frame church was built, which was dedicated on August 20, 1873.

He completed the church and built the parish school, St. Cecilia's Institute, staffed by the Sisters of Mercy, who also conducted a home for working women.

[9] Constructed of brick and terra cotta, building began in 1883 to designs by Napoleon LeBrun & Sons in the Romanesque Revival style; it was completed in 1877.

The "...façade includes a porch that is supported by ten red granite columns, above which are seven stained glass windows.

[6] A large terra cotta relief of St. Cecilia, playing an organ is embedded into an arched panel on the building’s central gable.

The AIA Guide to New York City (2010) describes the church as an "ornate brick and terra-cotta facade is one of East Harlem's special treasures.