El monarca francés Luis IX apoyó desde el primer momento a Teobaldo, casándole incluso con su hija Isabel (6 de abril de 1255). Igualmente le ayudaría a suavizar sus relaciones con Castilla, e influiría decisivamente y determinaría el reinado de Teobaldo II. Con el apoyo del monarca francés, Teobaldo volvió a Navarra dispuesto a imponer su autoridad; acompañado de un nutrido séquito de franceses, convocó a los ricoshombres en Estella para que le juraran fidelidad y le prestasen homenaje, como también lo hicieron las villas de Pamplona, Sangüesa, Olite y Tudela. En la misma junta de Estella se llegó a una concordia con el obispo pamplonés sobre las numerosas cuestiones pendientes entre éste y la corona, como era la cuestión de las jurisdicciones de la capital y los castillos de Oro y Monjardín. Asimismo, nombró senescal al champañés Geofroi de Bourlemont, quien ocuparía el cargo dos años, hasta 1257. Esta reunión de Estella señalaba cuál era la dirección política de su reinado: entendimiento con el poder religioso, relaciones de equilibrio con la alta nobleza y mano fuerte con los infanzones y caballeros. La burguesía, por su parte, constituyó un apoyo a las reformas administrativas y fiscales.
Fruto de las directrices de su suegro fue la paz pactada con Alfonso X de Castilla en Vitoria el 1 de enero de 1256, cediendo el castellano las plazas de Hondarribia y San Sebastián. Un año antes el rey de Francia había iniciado los preparativos para casar a Luis, su hijo primogénito, con Berenguela, hija primogénita del rey castellano Alfonso X, y Teobaldo II acudió a París como testigo del tratado firmado entre los embajadores de ambos reyes. Cuando el monarca navarro regresó a Navarra en 1255, no podía estar enfrentado a un aliado de su protector, de forma que se fueron relajando las hostilidades entre el rey navarro y el castellano. Afirmada la amistad navarro-castellana, se distendieron también las relaciones castellano-aragonesas. La única intervención bélica de su reinado fue la realizada en Gascuña en 1266 contra la corona inglesa, a causa de la incorporación de la Bigorra a la corona navarra.