High peak-to-average power ratio (PAPR) remains the main challenge of coherent optical orthogonal frequency division multiplexing (CO-OFDM) systems. Selective mapping (SLM) is a well-known effective PAPR reduction technique, but it suffers from high computational complexity. To reduce the PAPR of OFDM signals, a low-complexity, partition-recombined SLM (PRSLM) scheme is proposed. The PRSLM scheme can generate more candidate signals than that of the conventional-original SLM (COSLM) scheme. The real and imaginary components of time-domain symbols are first partitioned, and then recombined to generate new candidate signals, which reduces computational complexity significantly. A 40-GBaud single-polarization CO-OFDM transmission system is set up to evaluate the performance of the PRSLM scheme. Simulation results show that the proposed scheme achieves 61.9% reduction in complex multiplication complexity, and 60.3% reduction in addition complexity compared with the COSLM scheme when the FFT size is 128. Furthermore, the proposed scheme achieves a similar PAPR reduction performance to the COSLM scheme without bit error rate degradation. In a nutshell, the PRSLM scheme improves noise tolerance and implementation efficiency of high-speed optical communication as well as alleviates nonlinear impairments.