The phrase comes from vuestra merced, as other answers have noted, meaning "Your Mercy" or "Your Grace." It was a polite second person pronoun, conjugated in the third person like the modern usted. Usted first appears in writing in the 1600s, I believe.
There have been other polite ways of referring to other people in Spanish, however, that also precede usted.
The phrase "su merced" was used from at least the 1300s to refer to people with whom one had some degree of social distance, particularly those whom society labeled as superior. This form survives in sumercé, which is still used in some parts of Colombia.
The pronoun vos used to be the main polite second person pronoun, during the 1400s and 1500s. I believe it may also precede vuestra merced. If you watch the Spanish TV show El Ministerio del Tiempo, you'll see that one of the main characters is from that time period, and tends to call people he doesn't know by vos. This voseo still exists in many parts of the world, including countries such as Argentina. However, the meaning has changed, and it is now an informal pronoun. The old usage may still be preserved in Ladino or Haketia, a hybrid of Hebrew and Spanish spoken by some Jews of Spanish descent.
This word, vos, has an orthographically identical counterpart in Latin, which was however plural (i.e. what some people now would call vosotros - vos otros!), so it was probably the oldest. For the plural to singular shift, compare the English "Royal we" and the shift of you to singular.