A new approach named MPSO-TS, which combines the advantages of particle swarm optimization (PSO) in global search, Tabu search (TS) technique in local search, and the mutation operation in improving solution diversity, is presented in this study. Experimental result obtained with ten benchmark functions illustrates that the proposed MPSO-TS is superior to other optimization schemes. Further, MPSO-TS is applied to estimate the carrier frequency offsets (CFOs) of the uplink orthogonal frequency division multiple access (OFDMA) system. Experimental results indicate that MPSO-TS not only can achieve the best performance but also spends the minimum CPU time per generation as compared to the existing PSO-based optimization approaches.