La Parroquia se creó en el año 1981 por el entonces Obispo de la Diócesis D. Jesús Pla Gandía con la denominación de San Juan de la Cruz. Posteriormente, a petición de las Hijas de la Caridad, comunidad que estaba al frente de los servicios pedagógico-religiosos de los niños de la antigua Inclusa, para quienes se construyó el edificio, y debido a que coincidió la creación de la misma con el aniversario del nacimiento de San Vicente de Paúl, se puso también a éste como co-patrono y titular de la Parroquia.

Inicialmente tomó como sede la antigua capilla del Colegio de San José, cedida por la Excma. Diputación Provincial para este menester, junto con algunas habitaciones que facilitasen los diversos servicios pastorales de la Parroquia; pero con la condición de que todos los gastos que se originasen fuesen a cargo de la misma.

Pronto se vio que resultaba demasiado pequeña para la gran afluencia de los fieles y se pidió a la Diputación el permiso oportuno para ampliarla con dos capillas laterales. Concedido éste, se encargó a la empresa CUBIERTAS Y MZOV, S.A. la realización de dicha obra, bajo la inspección del personal técnico de la Diputación. De ahí la definitiva forma de cruz latina que presenta el templo.

Más tarde se rehicieron las escaleras de entrada debido al deterioro y empinamiento de las mismas. Finalmente, para facilitar el acceso a la Iglesia de los minusválidos, se construyo la rampa de acoso lateral.