The dynamic properties of long-span bridges with flexible and light-weight features are of critical importance in safety assessment and response prediction. The primary concern of this study was to infer the dynamic characteristics of long-span bridges subjected to vortex-induced vibration (VIV) by reasonably accommodating the fluid–structure interactions during VIV and the various uncertainties arising in the dynamic characterization of the structures due to measurement noise and modeling errors. By taking the advantage of advanced image processing techniques, the Farnebäck dense optical flow method was used to process the vibration video to extract the displacement time history. In contrast to conventional operational modal analysis (OMA) approaches, which are usually based on the white noise assumption, a new frequency-domain Bayesian method is proposed to make a statistical inference for the dynamic characteristics of the bridge based on the power spectral density of the VIV measurements and the Scanlan's empirical VIV model for bridge decks. A fast computation scheme is also proposed to achieve the posterior uncertainties of the modal frequency of the bridge, the structural damping of the bridge, and the total damping of the VIV system. The efficiency and the accuracy of the proposed algorithms have been verified with the VIV motion of a super long-span suspension bridge. Comparison with those identified using different OMA approaches in the time domain and the frequency domain is also be presented.