Originally a calque of Latin Deō grātias and/or a shortening of Gode sīe þanc (compare German Gott sei Dank).
Gode þanc