W-Salam,
When I was in Saudia, brothers from the Desert told me that traditionally in the Desert Turban is worn and part of it is used to cover the face/neck. Even in the 1977 movie (The Messenger) you will see them wearing Turbans and using them as face cover so this clearly tells that you that even until 1970's Turbans were used.
Shemagh is a pretty late fashion development.