Travel time is widely used to measure the effectiveness of transportation systems and becoming one of the most popular traffic information which travelers are interested in. The ability to accurately predict travel time in transportation networks is a critical component in advanced traveler information system (ATIS). This paper focuses on large-scale travel time prediction for urban arterial roads and proposes a new prediction method based on Kalman filter. To estimate the parameters in the method, the hierarchical clustering is used to gain the spatial relation of roads and the idea to estimate the state transition matrix from temporal and spatial perspectives separately is proposed. A large number of float car data in Beijing are used to evaluate the prediction method and the experiment results prove that it could predict travel time accurately.