A building fund campaign had been started in August of that year to raise $30,000 for the construction of a church edifice. In December, the church received an endowment of $4,000 toward the purchase of an organ for the future church. The endowment was donated by H.H. Heinrich of the H.H. Heinrich Co. of New York as a memorial to his wife, Elizabeth. Pastor Chapman said at the time that Mr. Heinrich was "unknown to the members of the church," but his gift made a favorable impression on them.
In June 1958, contracts were signed for the construction of the church, and a ground breaking ceremony was held July 22, with 200 persons in attendance. Soren B. Jacobsen of Lake Mohawk was the contractor, Robert Clothier of Newton was the architect. The new church would be of modern contemporary design, consisting of two buildings, joined by a long loggia. The main body of the church is designed with a steep roof, rising from seven to 57 feet. The plans also called for classroom and office facilities, and a fellowship hall with a kitchen. The hall was also to be used for Sunday School classes. The main church would seat approximately 250 persons.
Mr. and Mrs. Dahlen made another donation to the congregation, which allowed the addition of a chapel and Bible study room in the space between the church and the fellowship hall. The chapel was given as a memorial to Mrs. Dahlen's parents, the Rev. and Mrs. I.L.P. Dietrichsen. The Bible study room was designated as a memorial to Dr. Waiter A. Maier, well-known voice of the Lutheran Hour broadcasts, with whom Mr. Dahlen had been closely associated during the development of the program in the early 1930's.
Construction proceeded quickly and smoothly, and the cornerstone was laid during the worship service on October 12, 1958. A time capsule placed in the cornerstone contained a list of all communicant members of the church and biographies of the pastor, church council and building committee members, the architect and the builder. Also in the capsule were a Bible and a copy of that weeks New Jersey Herald.
The service began at the Grange Hall, and after the sermon, the congregation went to the building site for the cornerstone ceremony.
Redeemer Lutheran Church was dedicated May 31, 1959. The Rev. Dr. Louis Henze, former executive secretary of the Atlantic District, Lutheran Church-Missouri Synod, spoke at the 11 a.m. worship service, and the Rev. Nornan Temme, associate director of public relations of the Missouri Synod, was guest speaker at the 4 p.m. dedication vespers. The Rev. Hans Voss, circuit visitor, was liturgist, and the Rev. Waiter Reuning, vice president of the Atlantic District, was lector.
In December 1961, Pastor Chapman accepted a call to Good Shepherd Lutheran Church in Jamaica, N.Y. He had served the parish for seven years.
The Rev. Charles Ertman of Hackettstown served as interim pastor for several months.
The Rev. Arthur W. Lesslie, pastor of Grace Lutheran Church, Middletown, Conn., accepted the call to Redeemer and began his ministry here in June 1962. He stayed at Redeemer until 1971, when he accepted a call to St. Paul's Lutheran Church, Amityville. N.Y. During his pastorate at Redeemer, the congregation increased by 300 adults and children.