This paper studies the finite element (FE) model updating of an 18-story experimental structure. FE model updating requires solving optimization problems that are generally non-convex and have unknown number of local optima. For such problems, neither randomized local optimization algorithms nor stochastic search algorithms can guarantee global optimality. To obtain the global optimum and improve the accuracy of FE model updating, this paper proposes the branch-and-bound (B&B) algorithm for solving non-convex optimization problems in FE model updating. The paper focuses on the modal property difference formulation that minimizes the difference between experimental and simulated eigenvalues and eigenvectors. We propose a reformulation of the modal property difference approach using epsilon-constraint, to enable the application of the B&B algorithm in FE model updating. The proposed approach is first investigated in simulation and compared with the interior-point method and the genetic algorithm. The model updating results using the B&B algorithm are next validated by the shaking table test data of an 18-story steel frame structure.