Compressive sampling matching pursuit (CoSaMP), as a conventional algorithm requiring system sparsity and sensitive to step size, was improved in this paper by approximating the sparsity with adaptive variable step size. In the proposed algorithm (CoSaMP with variable step size abbreviated as Vss-CoSaMP), the idea of approximating sparsity with adaptive step size was borrowed from the sparsity adaptive matching pursuit (SAMP) algorithm to determine the sparsity for the CoSaMP algorithm. The applicability of the CoSaMP algorithm was therefore expanded considerably. On this basis, a step size reduction was added as the iteration termination condition of an orthogonal frequency division multiplexing (OFDM) system. An adaptive variable step size algorithm was then put forward to address the CoSaMP algorithm’s sensitivity to step size. It could realize the required precision at different initial step sizes. A simulation was carried out to analyze the influence of pilot number and step size in an OFDM system on the algorithm. The algorithms, including SAMP, CoSaMP, and Vss-CoSaMP, were compared with two sparse channels, revealing that the Vss-CoSaMP algorithm overcame the problem of the CoSaMP algorithm, that is, the impossibility to forecast the channel sparsity. With the adaptive step size, the proposed algorithm could reach and achieve better accuracy than the CoSaMP algorithm. Additionally, the proposed algorithm was superior over the SAMP algorithm in terms of reconstruction, mean square error (MSE), and bit error ratio (BER).