Disclosed are various embodiments for a distributed code tracing system that provides code tracing as a service in a multi-tenant computing environment. In one embodiment, a code trace is received that is associated with a request submitted to a particular application hosted in a computing environment, where multiple applications are hosted in the computing environment. The code trace documents calls to multiple component services of the particular application in order to respond to the request. The code trace is compressed using time-based compression. The compressed code trace is then stored in a data store that is indexed by a unique identifier of the request.