To address OP, the real name of Santa Fe is La Villa Real de la Santa Fe de San Francisco de Asis (Royal Town of the Holy Faith of St. Francis of Assisi). Santa Fe does indeed mean holy faith.
The city was actually founded some time between 1000 and 1100 by the Pueblo, but was only named Santa Fe when the Spanish re-formed the town in 1607.
NM was never a European kingdom. It was a province of New Spain at the time in question.
Source: Used to live there.