In 1967, a plot was acquired from the Lucknow Diocesan Trust Association by the late Bishop Raymond D’Mello on the Allahabad Faizabad Road, opposite to the Collectorate with the persuasive efforts of late Rev. Fr. Faustin Alva, the then Parish Priest (Rector) of St. Joseph’s Cathedral, Allahabad, wherein now the Karunashray hospital stands.

In 1968 the late Bishop Raymond D’Mello acquired another plot of land from Mrs. Florence Buchman in the Civil Line with a residence and a small Church in it. Bro. Paschal was the care-taker of the property till Rev. Fr. Stephen Rodrigues was appointed the first Chaplain.

The inauguration and blessing of the Church and the Convent took place on 1st July 1968 with the arrival of Rev. Fr. Stephen Rodrigues from Renukoot and Sr. Canice, the first Sister Superior, and her community of five Sisters of the Little Flower of Bethany, Mangalore. And thereafter the place came to be called the Catholic Mission, Sultanpur, and the convent was named as Stella Maris. Mrs. Ruth John and her three sons, members of the Methodist Church, received into the Catholic Church by Fr. Stephen Rodrigues and later Mr. John Gunny by Rev. Fr. J. B. Castelino, formed the core of the Catholic community of Sultanpur. The Church Bell came as a gift from the Mudila Mission.

Soon after, Fr. Stephen Rodrigues was given the responsibility of constructing a school building which he did by May 1970 and the Bishop handed it over to the Bethany Sisters to run an English Medium School to cater to the educational needs of the people of Sultanpur and the Christian community in particular.

The construction of the Karunashray Hospital on the plot acquired on the Allahabad Faizabad Road earlier began only in 1972. After the slow and unsteady progress due to the insufficient funds set aside by the late Bishop Raymond D’Mello, the completed hospital building was finally inaugurated on 9th February 1975 by the then Parliamentary Minister, Shri Kedarnath Singh, in the absence of the Bishop.

However, the formal blessing of the hospital and the new Parish House constructed by Fr. J. B. Castelino, was done on 17th March 1975 by Rt. Rev. Dr. Alfred Fernandez and the privilege of running the hospital went to the Ursuline Sisters of Mary Immaculate of Cannanore, Kerala.

From time to time the parish priests were appointed by the Bishop of Allahabad to serve the spiritual needs of the sisters of both communities and the small Catholic community of Sultanpur. The parish priest of Sultanpur is also givent he additional responsibility of a visiting station at HAL, Korwa, where Mass is offered on alternative Sundays for a small Catholic Community of Korwa and Amethi.

Some priests were posted here to do their B.Ed. studies as this facility was made available by the Head of the B. Ed. department of KNI at Sultanpur and Amethi.

On the occasion of the Silver Jubilee Year of the Catholic Mission, Sultanpur, in the year 1992, Dr. Eugene Rebello volunteered to sponsor a grotto to the parish Jubilee Memorial under the guidance of late Fr. John of the Cross D’Souza, while Fr. Thomas Serrao arranged the transport of the statue of Our Lady of Lourdes from Quilon, Kerala.

Rt. Rev. Isidore Fernandes, the then Bishop of Allahabad, blessed the grotto on the occasion of the Silver Jubilee celebrations of the Church as well as the Stella Maris Convent, held simultaneously on 29th November, 1992. On the suggestion given by late Fr. John of the Cross D’Souza, the Church was dedicated to St. Paul by the Bishop and thereby he renamed it again St. Paul’s Church, the only Church to be dedicated to St. Paul in the diocese.

Fr. Sebastian D’Cruz, during his tenure as the parish priest, took the initiative to build the present church with the encouragement and financial backing of Bishop Isidore Fernandes. The foundation Stone was blessed and laid by Fr. Sebastian D’Cruz on 26th May 1999 and it took about a year and a half for him to complete the building. The inauguration and the blessing of the church and the consecration of the altar was done by Rt. Rev. Isidore Fernandes in the presence of the diocesan priests, religious brothers and sisters and the faithful of the parish on 18th October, 2000.