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.