This paper is concerned with finite element model updating of rotating structures using measured vibration test data. The use of both deterministic and stochastic optimisation techniques was investigated in order to minimise the difference between the measured and analytical data. First, a theoretical basis was developed for frequency response functions (FRFs) updating techniques. The standard linear least-square (LLS) formulation was applied to the FRF updating formulation where the element mass, damping, gyroscopic and stiffness matrices are corrected by using a single multiplier, the so-called p-value. A new residue was then proposed and formulated to improve the convergence rate of the FRF-based model updating in the presence of noise. Next, two well-known stochastic optimisation methods that require no gradient and can achieve a global optimal solution in solving non-smooth and highly non-linear optimisation problems, namely genetic algorithm (GA) and adaptive simulated annealing (ASA), were introduced and implemented to the developed rotating structure code. The findings were illustrated in the case of a test rotor and the advantages and disadvantages of the proposed techniques were discussed in some detail.