In this paper, a novel method base on non-Markovian Fractional Brownian Motion (FBM) is proposed for Lithium-ion batteries remaining useful life (RUL) prediction. Firstly, the FBM degradation model is introduced and the Hurst exponent ( H ) is calculated. Secondly, the parameters of the FBM model are estimated by maximum likelihood estimation (MLE). The Fruit-fly Optimization Algorithm (FOA) is proposed to optimize the H . Then the procedure for RUL prediction is provided. Capacity degradation data of Lithium-ion batteries is selected as prediction case, and the RUL prediction results are given by two real cases of RUL prediction for lithium-ion batteries. The validity of the proposed method is verified by several evaluation criteria.