We propose and evaluate a novel approach for automatic parallelization. The approach uses traces as units of parallel work. We discuss the benefits and challenges of the use of traces and propose an execution model for automatic parallelization based on traces. We implement a system that demonstrates the benefits and addresses the challenges of using traces for data-parallel applications in an offline feedback directed system. Finally, we evaluate our system by using it to automatically parallelize three sequential programs that exhibit data-level parallelism from the Java Grande benchmark suite. The resulting performance compares favorably to the performance achieved by hand parallelized versions of these programs. Thus, we demonstrate the viability of trace-based parallelization.