Methods, systems, and computer-readable media for implementing distributed trace storage in a service-oriented system are disclosed. A plurality of trace events are generated for a plurality of service interactions between individual ones of a plurality of services. The services are implemented by a plurality of hosts. Individual ones of the trace events comprise respective trace identifiers. The trace events are stored at individual ones of the hosts at which the respective trace events were generated. In response to a request from a trace analysis system, a portion of the trace events are retrieved and sent from individual ones of the hosts to the trace analysis system.