Exploring the content of large execution traces can be a tedious task without efficient tool support. Building efficient trace analysis tools, however, requires a good understanding of the complexity embedded in traces. Trace complexity has traditionally been measured using the file size or the number of lines in the trace. In this paper, we argue that these metrics provide limited indication of the effort required to understand the content of a trace. We address this issue by introducing new trace complexity metrics based on the concept of entropy. Our metrics measure two important aspects of an execution trace: repeatability and variability. We present a case study where we apply the metrics to several execution traces. A discussion on how we can reduce the complexity of a trace based on these metrics is also presented.