This article presents a novel fractional order LMS (FOLMS) algorithm, which involves a variable gradient order scheme. The fractional order gradient descent method is revisited firstly. A variable initial value scheme is proposed to attenuate the non–locality of fractional order calculus and to ensure the convergence of the proposed FOLMS algorithm. Furthermore, it is noticed that a contradiction between rapidity and accuracy always appears together with the advancement of FOLMS algorithm; namely, a larger value of the gradient order can not only give a faster convergence speed, but also correspond to a larger estimation error. For the purpose of removing the contradiction between rapidity and accuracy, a variable gradient order scheme is designed for the FOLMS algorithm. Based on a sufficient large number of independent runs, the efficiency and superiority of the proposed algorithm are demonstrated in numerical examples finally. •Fractional order gradient decent method with variable initial value is developed.•Fractional order LMS (FOLMS) with variable initial value is proposed.•The performance of the proposed FOLMS is analyzed.•FOLMS with variable gradient order is constructed.