A pair of waveforms with good auto- and crosscorrelation properties is required in simultaneous polarimetric radar. Complete complementary sequence (CCS) has ideal range sidelobes along the zero Doppler axis, which is desirable in polarimetric radar. However, CCS is not widely used due to its sensitivity to the Doppler shift. In this letter, a L-BFGS (Limited Memory Broyden Flecher Goldfarb and Shanno) iterative method of constructing CCS with high Doppler tolerance is proposed, by which the range sidelobes can be suppressed in certain Doppler shifts. Numerical results are shown to demonstrate that the sidelobe peak of the designed CCS is about 30 dB lower than that of the CCS designed by the state-of-the-art GPTM (Generalized Prouhet-Thue-Morse) method in a certain Doppler shift interval.