The four districts of Orissa, i.e, Balasore, Bhadrak, Mayurbhanj and Keonjhar, were under the Archdiocese of Calcutta till 1968. Christianity began in Balasore probably during the years 1859 -1865 when church activities were started by Fr Chrysanthus Depart in Midnapur - Balasore area. He settled down at Balasore in 1865. From 1865 till 1936 the Jesuit Fathers residing at Balasore and Krishnachandrapur looked after the Church in Balasore. From 1936 onwards till 1938 there were no residential priests in Balasore and the two church work stations were looked after by the Jesuits of Balasore. Due to an earthquake the church was damaged and later completely dismantled. The Fathers left for Malta and gradually many Christians left Balasore. In 1948 Fathers Vizjak, a Jesuit Priest, resided at Krishnachandrapur and Balasore alternatively and cared for the needs of the little community which stayed back. From 1964 till 1968 Diocesan Priests from the Diocese of Cuttack rendered their services in Balasore, Krishnachandrapur and in Barbil at the request of the Archbishop of Calcutta.

On June 8, 1968, the Holy See separated the above mentioned three districts from the Archdiocese of Calcutta and formed them into one unit named "Prefecture of Balasore", annexing it to the ecclesiastical Province of Cuttack-Bhubaneswar. The new Prefecture is entrusted to "Congregation of the Mission". (Vincentians).

On June 14, 1968, Bp Jacob Vadakeveetil, cm, of the Congregation of the Mission was appointed the first Apostolic Administrator and took charge on November 18, 1968. On January 13, 1990 the Prefecture Apostolic was raised to the status of a diocese and Bp Thomas Thiruthalil, cm, was appointed its First Bishop.