Because the partial transmit sequence (PTS) peak-to-average power ratio (PAPR) reduction technology for optical orthogonal frequency division multiplexing (O-OFDM) systems has higher computational complexity, a novel two-stage enhanced-iterative-algorithm PTS (TS-EIA-PTS) PAPR reduction algorithm with lower computational complexity is proposed in this paper. The simulation results show that the proposed TS-EIA-PTS PAPR reduction algorithm can reduce the computational complexity by 18.47% in the condition of the original signal sequence partitioned into 4 sub-blocks at the remaining stage of n-d=5. Furthermore, it has almost the same PAPR reduction performance and the same bit error rate (BER) performance as the EIA-PTS algorithm, and with the increase of the subcarrier number, the computational complexity can be further reduced. As a result, the proposed TS-EIA-PTS PAPR reduction algorithm is more suitable for the practical O-OFDM systems.