Looking back on historical GHC releases, the earliest one available on the web page is version 0.29, released in July 1995, and it already has the trace function. I would guess has been there for a long time.