Per our FAQ section on time-traveling communication:
Of course and as always, more can be said, if anyone has something else they want to contribute.
Surprisingly far! Probably farther than the concept of Spanish as a language. So, to answer this, I'll give a quick overview of Spanish as it developed from Classical Latin and give a description of how easy it would be to communicate.
Starting with Classical Latin. Mutual intelligibility is pretty low here. The biggest issue is actually grammar. Latin had a complicated case system, meaning that nouns varied in form based on what role they played in the sentence.
Think how English distinguishes I, me, my, but for all nouns. So a word like carne would've had the forms carō, carnem, carne, carnis, carnī. This system did not survive into the modern Romance languages, Spanish included (Romanian has a very simplified and different version of it though).
Instead prepositions are used; in Latin, a meat party would be fēstum carnis but Spanish would say una fiesta de carne, with that de communicating what would have been a different noun form in Latin. This also means that word order was much more flexible, carnis fēstum is also fine, but in Spanish, though the word order is much more flexible than in English, it's nowhere near as malleable as in Latin.
There are also substantial differences in vocabulary, many Spanish words existed in Classical Latin, but they had different meanings. estar comes from Latin stāre, but instead of a copula verb, it meant to stand.
Pronunciation was also different, though not extremely different. For example, take a word like ayudó (he/she/it helped), this comes directly from the form of the verb in Latin, but is barely recognizable, adiūtāvit.
Classical Latin, though, eventually became Late Latin. Now, we can talk about two things here, the attested changes in Latin which we can see in texts like the Vulgate Bible and the writings of folks like St. Augustine. The problem here is that folks tried to emulate older versions of speech when writing.
So it's possible that in speech, things had already changed that wouldn't be reflected in writing until much later. Look at a word like knight in English, both the <k> and <gh> are silent, but they weren't when that spelling was developed. English here is retaining the traces of older phonology in its writing, Late Latin was much the same. But we can also talk about Proto-Romance.
Proto-Romance is less a language and more a concept. It is the common ancestor of the Romance languages and was developed using a comparative analysis of modern Romance languages. So it only shows the aspects of Latin that survived in its descendants. So it can't tell us exactly how people actually spoke, but by combining it with what we know about Late Latin, we can get an idea of how people spoke.
Late Latin is a lot easier for a Spanish speaker. The case system had been simplified and prepositions had already become more common. I would say mutual intelligibility is about as high as between Spanish and Romanian.
The "late" in Late Latin is a modern concept, speakers of Latin in Iberia continued to be Latin speakers until around the 10th century when they started to emulate their neighbors in France and call the spoken vernacular Romance and distinguish it from the written form that still looked to Classical Latin as a model. This also means that we don't really know what spoken speech was like, because the vernacular wasn't used for writing.
By the time the term Romance comes into use and we start to have written texts, Spanish is already recognizable and a Modern Spanish speaker could probably get by. The differences are mostly phonological, but there are a few grammar differences, though these are mostly cosmetic, think reading Shakespeare.
El Cantar del Mio Cid, written in the 12th century is perfectly readable for a modern Spanish speaker. There are some differences, but nothing insurmountable. The pronunciation might be a bit tough, but not impossible.
So, I'd say a Modern Spanish speaker could communicate with someone as far back as the point when Spanish started to be considered separate from Latin, around the year 1000.