This paper proposes a new method in construction fuzzy neural network to forecast travel speed for multi-step ahead based on 2-min travel speed data collected from three remote traffic microwave sensors located on a southbound segment of a fourth ring road in Beijing City. The first-order Takagi-Sugeno system is used to complete the fuzzy inference. To train the evolving fuzzy neural network (EFNN), two learning processes are proposed. First, a K-means method is employed to partition input samples into different clusters and a Gaussian fuzzy membership function is designed for each cluster to measure the membership degree of samples to the cluster centers. As the number of input samples increases, the cluster centers are modified and membership functions are also updated. Second, a weighted recursive least squares estimator is used to optimize the parameters of the linear functions in the Takagi-Sugeno type fuzzy rules. Furthermore, a trigonometric regression function is introduced to capture the periodic component in the raw speed data. Specifically, the predicted performance between the proposed model and six traditional models are compared, which are artificial neural network, support vector machine, autoregressive integrated moving average model, and vector autoregressive model. The results suggest that the prediction performances of EFNN are better than those of traditional models due to their strong learning ability. As the prediction time step increases, the EFNN model can consider the periodic pattern and demonstrate advantages over other models with smaller predicted errors and slow raising rate of errors.