According to the OED, the word "god" appeared first in a 9th century manuscript called the Vespasian Psalter. If you care to expand the question to other languages, the Gothic word guþ is related, and is attested a few centuries earlier. It isn't possible to trace the root back further, because its pre-Germanic etymology is uncertain.

The earliest use of "god" with the modern spelling is given as being in one of the Wycliffite Bibles, dating to 1382.