A methodology is presented for Bayesian structural model updating using noisy incomplete modal data corresponding to natural frequencies and partial mode shapes of some of the modes of a structural system. The procedure can be used to find the most probable model within a specified class of structural models, based on the incomplete modal data, as well as the most probable values of the system natural frequencies and the full system mode shapes. The method does not require matching measured modes with corresponding modes from the structural model, which is in contrast to many existing methods. To find the most probable values of the structural model parameters and system modal parameters, the method uses an iterative scheme involving a series of coupled linear optimization problems. Furthermore, it does not require solving the eigenvalue problem of any structural model; instead, the eigenvalue equations appear in the prior probability distribution to provide soft constraints. The method appears to be computationally efficient and robust, judging from its successful application to noisy simulated data for a ten-storey building model and for a three-dimensional braced-frame model. This latter example is also used to demonstrate an application to structural health monitoring.