In this paper, we develop a new structural identification algorithm by improving the defect of the classical Monte Carlo Filter (MCF). In the MCF, we identify the probability density function of the state vector which is approximated by many realizations, called particles. In the classical MCF, however, as the degree of freedom of structural model increases, we have to generate exponential order of particles. This results in extreme increase of computation time. To overcome this problem, we developed the relaxation MCF (RMCF) in which we improve the filtering process of the classical MCF. By using this method, we can reduce computation time drastically. Moreover, we developed the GA-RMCF, in which we combine the Genetic Algorithm (GA) with the RMCF. We apply the proposed algorithm, the GA-RMCF, to identifying the dynamic parameters of a five-story model building using observed data obtained through the shaking table tests. The data processed here are from a linear structural model.