The seemingly computational burden of state space model identification has limited its real-time application though it offers some important advantages over methods based on input-output transfer functions. It has been shown recently that ideas from the theory of displacement structure can be used in state space identification to reduce the computational burden of batch processing from O(MN(2)) to O(MN) flops when the data matrix is of size M x N, where N > M. However, in many on-line identification scenarios with slowly time-varying systems, it is desirable to update the model as time goes on with the minimal computational burden. In this paper, we extend our results of the batch processing algorithm to allow updating of the identified state space model with O(M(2)) flops. Again, the theories of displacement structure and of the fast subspace decomposition (FSD) technique play crucial roles in the realization of the fast updating algorithm. Some computer simulation results are also presented.