A peak-to-average power ratio (PAPR) reduction method for an orthogonal frequency division multiplexing (OFDM) system based on a combination of a partial transmit sequence (PTS) scheme with the backtracking search optimization algorithm (BSA) is proposed. The PTS scheme shows good PAPR reduction performance; however, it requires a complex computation to search the set of optimum phase factors, especially for high-speed data transmissions. To minimize the complexity of the search for optimum phase factors, the PTS scheme is combined with the BSA. The BSA is a new and efficient population-based evolutionary search algorithm for real-valued optimization problems. A set of simulations is conducted for the PAPR reduction performance and computational complexity comparisons of the BSA-PTS scheme with different PTS schemes. Simulation results indicate that the BSA-PTS scheme yields an effective PAPR reduction performance with low computational complexity.