A tracing system that provides automated tuning of execution tracing by adjusting the collection of trace data is described. In one embodiment, the user sets an initial tracing profile for a tracing program. In addition, the user sets an upper limit for the tracing performance penalty. The auto-tuning system monitors the performance penalty induced by tracing and, when the performance impact is excessive, removes trace points that are causing the most impact on performance. Auto tuning is especially useful for performing software recording in mission-critical and/or time-critical applications, such as servers, real-time applications, etc. The system typically adjusts relatively quickly such that most users do not feel the influence of the tracer.