The idea of a new Cathedral church in the city of Newark was first proposed by Bishop Bayley in 1859, only six years after he had been appointed bishop of the new diocese by Pope Pius IX. Bishop Bayley, a convert from the Anglican Communion and nephew of Saint Elizabeth Ann Seton, took the first formal steps in making his dream a reality when he purchased a plot of land on the comer of High and Kinney Streets on January 17, 1859. This site and an alternate site at South Park and Broad Streets were rejected by the bishop in favor of the present plot of land, measuring two hundred feet by eight hundred feet, and bounded by Park and Sixth Avenues, Clifton Avenue and Ridge Street. Bishop Bayley decided to make the purchase after the Park Avenue lot was recommended by Jeremiah O'Rourke, architect and trustee of Saint Patrick's Cathedral on Washington Street and Reverend Monsignor George Hobart Doane, pastor of Saint Patrick's and himself the son of New Jersey's Episcopal Bishop, the Right Reverend G.W. Doane. Father Doane favored the new site because it "commands a view of the Orange Mountains on the west and Newark Valley, the hills of Staten Island, and New York on the east. "

The actual transaction, for the sum of sixty thousand dollars, was executed on January 2, 1871, when Bishop Bayley acquired a deed from owners Peter T. Doremus and Hiram M. Rhodes. Prior to this, in April, 1870, Father Doane and Mr. O'Rourke, who would ultimately be selected as the Cathedral's first architect, traveled to Germany, France and England at Bishop Bayley's request, to gather ideas for Newark's proposed Diocesan Church. After studying several cathedrals in England and on the continent, Mr. O'Rourke met in London with George Goldie, one of the leading proponents of the neo-gothic revival. Several meetings between the two men resulted in the sketching of plans for a church much smaller than the present Cathedral. No know record of the original O'Rourke/Goldie proposal exists, but we do know that O'Rourke ultimately abandoned them in favor of a much more comprehensive plan adopted in 1897.

Following Bishop Bayley's elevation to the See of Baltimore in 1872, the Cathedral project was passed on to his successor Michael Augustine Corrigan, who authorized excavation of the site under Mr. O'Rourke's direction in 1875 and 1876.

But it was not until the arrival of Newark's third bishop, Winand Michael Wigger, selected in 1881, that the project actually got off the ground. Bishop Wigger, who was elevated to the episcopacy after Bishop Corrigan had been chosen Archbishop of New York, rejected all suggestions to sell the property, including an offer from the City in 1896, which had hoped to obtain the Cathedral site for the new Barringer High School. Instead, Bishop Wigger moved ahead, selected the Cathedral's patronal designation, "Sacred Heart", and erected a parish to serve the immediate area under the same title on February 15, 1889. Construction of a small church and school soon followed.