Two new gradient-based variable step size least-mean-square (VSSLMS) algorithms are proposed on the basis of a concise assessment of the weaknesses of previous VSSLMS algorithms in high-measurement noise environments. The first algorithm is designed for applications where the measurement noise signal is statistically stationary and the second for statistically nonstationary noise. Steady-state performance analyses are provided for both algorithms and verified by simulations. The proposed algorithms are also confirmed by simulations to obtain both a fast convergence rate and a small steady-state excess mean square error (EMSE), and to outperform existing VSSLMS algorithms. To facilitate practical application, parameter choice guidelines are provided for the new algorithms.