We had a discussion going in the Travel Chat about where the Arabic language originated (assuming borders had stayed the same throughout history).
Some websites have suggested Egypt, others Yemen, and one speaker of the language in the room agrees with the Yemen view, and I was hoping Linguistics.SE could provide some solid evidence for where it may have originated?
(by modern-day country, for example, if it originated in what was then called Siam, the answer today would be Thailand)
Where a certain language originated depends in large part on how exactly you define that language. Taking English as an example, one might wonder whether English as spoken in the 10th century is the same language as spoken nowadays - 10th century English is hardly intelligible to modern speakers of the language. But the name "English" is usually used to refer to the language no matter how dramatically it changed up until the point when it diverged from other Germanic languages (around the 6th century AD).
Looking at the history of Arabic in the same way, the first evidence of (Proto-)Arabic after it split from its ancestor (Central Semitic) comes from what is nowadays Saudi Arabia. The absence of any earlier written records from other regions does not prove that Arabic was not spoken earlier in other places, but this is the best piece of positive evidence that we have.
Of course it is true, as jlawler pointed out in a comment, that Arabic ultimately goes back to the Afro-Asiatic family, whose proto-language was spoken earlier in another place, possibly modern-day Nigeria. But I don't think this is a meaningful answer to the questions where Arabic originated. Using the same argument we would have to conclude that Latin, English, Danish, Hindi and Russian all originated from the same place, probably somewhere in western Asia - since they all belong to the Indo-European family. I don't think this is what people mean when they say "language x was first spoken in place y".
However, there is an important point in this. What we consider Arabic or English is not a monolithic language, but there are dialects. Not all of these dialects are mutually intelligible, and in the future some of these dialects might become languages of their own. The fact that the dialects of Arabic are considered to belong to a single language has more to do with politics and its status as the sacred language of Islam (similar points could be made with respect to a number of other languages).
If we were to consider Arabic dialects to be independent languages then the answer to the question "Where did dialect x of Arabic originate?" would of course be different. In that sense, where a language was first spoken depends on your understanding of what that language is, and whether you consider some dialects to be independent languages (or the other way around, you might consider what others think are independent languages to be dialects of a single language).
If you would like to keep the question what a dialect and a language is out of the debate then it is indeed necessary to go back to the last identifiable proto-language, in this case Afro-Asiatic. However, this is only the oldest ancestor of Arabic that can be identified with some certainty. It is likely that all languages go back to one proto-language, or at least a small number of proto-languages. We don't know yet where exactly these were spoken and might never know. Obviously, this would make questions as to the geographic origin of different languages pointless.
So if you want to have a meaningful answer to the question where Arabic originated you have to keep in mind that this depends on what you consider the Arabic language to consist of. If you agree with the majority usage of the concept "Arabic" then Saudia Arabic seems like the best answer, given the current state of archaeological evidence.
Old Arabic, the oldest attested form of the Arabic language, evolved on the territory of the Nabatean kingdom comprising parts of the territory of the following modern countries: Egypt (Sinai), Israel, Palestine territories, Jordan, Syria, and Saudi-Arabia (the northwestern corner). The capital city of the Nabatean kingdom was Petra, Jordan.
Since the original question mentions Yemen: There, a different group of semitic languages called Old South Arabic was spoken. The Old South Arabic languages aren't the predecessors of modern Arabic (and not even the predecessors of Modern South Arabic).
The Semitic language family include: Hebrew, Aramaic, Arabic, and Amharic to name a few. Hebrew predates others, and can be traced back to present day Israel. To say that Arabic "originated" in Saudi Arabia, or going back farther to a proto-language is to misunderstand how languages evolve, and the specific nature of Arabian nomadic tribes that spoke Semitic dialectal offshoots more than 4500 years ago. In terms of time, that is a beginning benchmark: approximately 3000 BCE. In terms of place, many present day Middle Eastern countries (as far as tribal regions can be recorded / connected to civilizations) do establish a historical context for claiming early Arabic was spoken in place y, at time x. I would be hard-pressed to accept a claim of origin simply based on dates and townships; the living word is far more organic, and accents are too geographically lucid to be pinned down by an x-y.
Classical & pre-Islamic Arabic were fundamentally changed by the revelation of the Quran. No doubt, it was into that highly refined oral society - which had indeed established and perfected a standard of Arabic - that Quranic verse was recited to and received by the public. This dramatically changed the way Arabic dialects would give reverence to the scripture forever. It also gave one of the clearest breaks for periodizing an historical linguistic evolution.
