Way back in the times of the Latin language, there were two different verbs, but not with the same meaning as today:
sum, es, esse, fui1, meaning "to be" (Spanish: "ser", "estar", "haber"). This was the main copulative verb in old Latin, i.e. it was used to connect two words or clauses. It was used also as an auxiliary verb. We use haber ("to have") as the auxiliary verb in modern Spanish. (Italian still uses the verb essere as an auxiliary.)
stô, -âs, -âre, stetî, statum, meaning "to remain" or "to stand" (Spanish: "estar de pie"). This is the tricky part. This verb (infinitive: stâre) is the ancestor of the modern Spanish estar, and is a cognate of the English verbs stay and stand. If you think about it, when you are standing, you are positioned in a given place at a given time. That is precisely the main difference between ser and estar. The latter can be taken to mean the same as ser, but at a given moment in time.
So these two verbs are the roots of today's ser and estar. But the DLE says that ser comes from seer, so what verb is that? Seer is an evolution of the Latin verb sedere, "to settle" or "to sit" (Spanish: "estar sentado"), by the loss of the middle -d- (something not uncommon) and the final -e (as happened with every verb in the Iberian Romance languages). As Vulgar Latin evolved, the verb seer merged with the old Latin verb esse (now essere), and soon the verb seer lost the meaning of "being seated," just as the verb stare lost the meaning of "being in a standing position." But both of them kept, respectively, the sense of being permanent ("ser") and being transitory ("estar").
More specifically, the essere verb denoted essence, while the stare verb denoted state.
So, sentences from Latin (that used the esse verb), such as
Vir est in foro (The man is in the marketplace)
(H)omo stat in foro
which now uses the verb stare, since what was perceived was that the man was standing in the marketplace. As time went by, the verb began to be used just to express that someone was in a given place at a given time.
Thus, we come to the age of Old Spanish, the 10th century onwards. Time to cite the most famous story from these years: Cantar de Myo Çid:
Grado a ti Sennor Padre que estas en alto.
Y estava donna Ximena con çinco duennas de pro, rogando a san Pero e al Criador.
These examples show that the verb estar (now the final -e was dropped) was being used the same as the nowadays version, both to mean being in a place and as an auxiliary verb for the continuous present (estaba rogando).
The verb ser also had already its current infinitive form, but was still used as an auxiliary verb in place of today's haber. But it was used already to form the passive voice. Examples:
En yra del rey Alffonsso yo sere metido.
Assi es vuestra ventura, grandes son vuestras ganançias.
Nonetheless, we still see some expressions that contradict the current way:
[...] en vuestras manos son las arcas.
But this could be because here the verb ser is used to mean to have: in fact the English translation reads ye have the coffers two.
You can find much more information about the uses of the verbs ser and estar in the Old Spanish in "Ser" y "estar". Orígenes de sus funciones en el «Cantar de Mio Cid» from Spanish writer José María Saussol (publicaciones de la Universidad de Sevilla, 1978). Abstract here (PDF).
1: Fui (Latin - the Spanish is a descendant) is unusual as it comes from the Proto-Italic stem *fu- "to become". Source