Su construcción se decidió el 23 de mayo del año 1686, en vista del estado de deterioro en que se encontraba la antigua iglesia. Las trazas del edificio se encargaron a mosén Juan Aparicio, en aquellos momentos maestro de la obra de la colegiata de Xàtiva. El 19 de febrero de 1693, frey Luis Gozalbo, rector de Montesa y prior de San Sebastián en la Orden de Montesa, colocó la primera piedra del nuevo templo, finalizando las obras en 1702. El campanario, que seguramente formaba parte del recinto amurallado de la villa, es el único elemento anterior al actual edificio, y fue construido, muy probablemente, durante los años ochenta del siglo XVI, aprovechando obras de ampliación de la iglesia de entonces. Cuenta con cuatro campanas en las ventanas principales, dos de ellas antiguas, de 1751 y 1790.
Por otra parte, la decoración original del interior de la iglesia se basaba en ángeles, hojas de acanto y toda serie de elementos de talla, siguiendo la pauta ornamental de las iglesias valencianas del último tercio del siglo XVII. Hoy subsiste de aquella ornamentación barroca la capilla del trasagrario y algunos elementos aislados, ya que el templo se vio afectado por los terremotos de 1748 y por una desafortunada intervención a mediados del siglo XIX. Los colores de aquella actuación se eliminaron en 2002, pintando los muros y la bóveda de la iglesia de acuerdo con criterios más rigurosos.
Se conservan, no obstante, una serie de obras de arte valiosas. En primer lugar hay que hablar del mueble del órgano, de autor anónimo, cuyo instrumento, restaurado en 2001, realizó en 1744 el organero Martín Usarralde.
En las capillas laterales se exponen una serie de cuadros muy interesantes. Así, al abrir la puerta derecha de la cancela, una vez dentro del templo, nos encontramos con la capilla del bautismo, con la antigua pila realizada en mármol de Buscarró en el siglo XVIII. Enfrente, un lienzo de escuela italiana, del siglo XVII, con la figura de San Juan Bautista y el bautismo de Cristo en la parte inferior derecha.
Tras dejar la capilla de San José, nos encontraremos con una pintura sobre tabla que representa el Calvario, realizada durante el primer tercio del siglo XVI por el llamado mestre de Xàtiva/Artés/Borbotó.
A continuación, procedente de la ermita de San Sebastián, podemos contemplar un retablo dedicado al patrón local, san Sebastián, ejecutado en 1559 por Gaspar Requena, un pintor nacido precisamente en Montesa hacia 1515.
Por otra parte, la capilla situada frente al San Sebastián, acoge el retablo de las Ánimas, de Vicent Requena, hijo del anterior. En el presbiterio, una pila del siglo XIV nos habla de la pertenencia de Montesa a la orden de su nombre, al traer en su fuste los escudos de la Orden, las armas reales y los escudos de las familias Tous y March. Los muros laterales se adornan con dos cuadros, el de la parte de la Epístola, atribuido al pintor José Amorós, se ejecutó durante la primera mitad del siglo XVIII. Presenta Santa María de Montesa con las santas mártires Águeda y Lucía, y bajo la virgen podemos ver Montesa todavía amurallada y con el castillo en pie; el situado enfrente, con la Resurrección del Señor, se atribuye al pintor valenciano Vicente Salvador Gómez (1637-1678).
El retablo del altar mayor es una réplica del ejecutado antes de la guerra, que databa del año 1765. En el nicho principal se venera una copia de la antigua imagen de la Mare de Déu que había en la iglesia del castillo, cedida por los freiles de la orden de Montesa a la parroquia después de los terremotos de 1748. La orfebrería que adorna la imagen pertenecía a la antigua, y data de los siglos XVIII i XIX.
La capilla barroca del trasagrario, con su decoración seiscentista in situ, guarda en un armario con las puertas decoradas por una lámina de plata cincelada los relicarios de la Santa Espina (1785) y el del Lignum Crucis (s. XV-XVI). También se conserva un cáliz de plata sobredorada, del primer tercio del siglo XVI y otros tres cálices del siglo XVIII, uno de ellos con la inscripción Soy de San Visente de la Villa de Montesa. A los tres días de abril del año del Señor de 1733.
En la sacristía se conserva un Calvario sobre tabla de finales del siglo XV, atribuido al Mestre de Xàtiva o escuela. También es muy interesante el aguamanil, labrado en mármol de Buscarró durante el siglo XVIII.
