Tudela es conquistada a los musulmanes en 1119 por Alfonso I el Batallador, rey de Aragón y Navarra, readaptando la antigua mezquita al culto cristiano. Para el año 1204, fecha de consagración de la cabecera del nuevo templo regido por priores y abades de Santa María sujetos a la Regla de San Agustín, las obras de la Colegiata están ya muy avanzadas.
En el año 1239, secularizada la iglesia, aparece el primer Deán o cabeza del Cabildo, que regía la vida de la entonces colegial de Santa María y que tenía jurisdicción cuasi episcopal en su territorio. Prueba de la importancia de los personajes que ostentaban el cargo, es el haber conseguido en 1258 que el Papa Alejandro IV concediese al deán tudelano el uso de anillo y mitra episcopal, lo que casi los equiparaba a los obispos de Tarazona de cuya diócesis dependía la iglesia de Tudela. No es de extrañar que se decidiese ir más allá de la equiparación mediante la construcción de un palacio, sede de los deanes, comenzando la construcción en 1477. A este periodo corresponden seguramente su cuerpo básico con las dos alturas actuales, la galería de arquillos ojivales con su claro estilo mudéjar de ladrillos diagonales en vuelo, y, tal vez, la torre mudéjar que fue demolida en 1879. Don Pedro de Villalón y Calcena, el más famoso de los deanes tudelanos, fue camarero pontificio y protonotario apostólico del Papa Julio II, quien no sólo confirmó sino que aumentó los privilegios otorgados a los deanes de Tudela. A esta época, primer cuarto del siglo XVI, corresponde la mayor ampliación del Palacio que experimentó grandes modificaciones pasando a convertirse en la principal casa de la ciudad y, por tanto, el lugar elegido para servir de acomodo a reyes y Papas a su paso por Tudela. Entre estas modificaciones destaca especialmente la decoración plateresca y el escudo de la fachada principal de la calle Roso.
A finales del siglo XVIII, como consecuencia de la creación de la diócesis de Tudela en 1783, se llevan a cabo nuevas reformas para mejorar su habitabilidad con el fin de hospedar al primer Obispo. Más tarde, en el siglo XIX, se le adosa un cuerpo hacia la Plaza de San Jaime, convirtiéndose, a partir de entonces, en la entrada principal del Palacio.
Desde el siglo XIX hasta la década de los 30 en el siglo XX, el caserón estuvo casi abandonado, momento en el que fue ocupado por diversos colectivos relacionados con la Iglesia. De esta forma el Palacio llega hasta los últimos años del siglo XX, y debido a su mal estado de conservación, se decide su restauración con el fin de devolverle su antiguo esplendor, siendo inaugurado el 26 de junio de 2000. Desde entonces miles de personas han tenido la oportunidad de disfrutar de este bello edificio, en el que se ubica el Museo de Tudela.