This paper proposes regularized version of Variable Step Size Normalized Least Mean Square algorithm (RVSSNLMS) for iterative channel estimation scheme in MC-IDMA system. The proposed scheme is based on the exploitation of the inherent sparsity in the OFDM channels. The performance of the proposed scheme is validated in comparison with the earlier proposed channel estimation schemes based on the Least Mean Square (LMS) Algorithm, Normalized Least Mean Square (NLMS), Variable Step Size Normalized Least Mean Square (VSSNLMS) algorithms and the and non-iterative CTF estimator and CIR predictor earlier proposed in literature. From the simulation results, the proposed RVSSNLMS based channel estimator outperforms the other three adaptive algorithms-based channel estimators in terms of BER and MSE, and at the same time exhibits lower computational complexity in comparison with the computational complexities of its counterpart, the non-iterative CTF estimator and CIR predictor