This paper proposes an efficient low-complexity polyphase interleaving and inversion (PII) scheme based on enhanced parallel tabu search (TS) for the reduction of peak-to-average power ratio (PAPR) in space-frequency block-coded orthogonal frequency-division multiplexing (SFBC-OFDM) systems. PII is a technique that can significantly reduce the PAPR of SFBC-OFDM symbols by exchanging SFBC symbols between subcarriers and inverting SFBC symbols. The optimal PII scheme, however, requires an exhaustive search over all combinations of subblockwise PII, whose computational complexity (CC) increases exponentially with the number of subblocks. To reduce the CC while offering low PAPR, this paper formulates the PAPR reduction with the PII technique as a combinatorial optimization problem, and then proposes using enhanced parallel TS to search for an optimal combination of subblockwise PII. Simulation results reveal that the proposed parallel TS-based scheme can have a PAPR only 0.0103 dB higher than that of the optimal PII scheme, while its computation load is only 2.2888% of the optimal one. This demonstrates that the proposed scheme can be an efficient alternative method to significantly reduce the PAPR of SFBC-OFDM signals while enjoying extremely low CC.