The Hebrew Bible (Tanakh, Christian Old Testament) recorded women wearing veils as early as Rebekah in Genesis (Breshith). See Judaism stack exchange
However, there is debate over whether women wore veils in public for modesty as currently done in the Middle East. As often the issue, historic records assumed the reader knew the customs and didn't describe the customs in detail.
Are there other ancient records (e.g. Egyptian pictures, text, cuneiform tablets, etc.) that give clearer indication of early Middle Eastern customs on wearing veils that can answer this question?