This paper is focused on an assessment of the state of the art of operational modal analysis (OMA) methodologies in estimating modal parameters from output responses of nonlinear structures. By means of the Volterra series, the nonlinear structure excited by random excitation is modeled as best linear approximation plus a term representing nonlinear distortions. As the nonlinear distortions are of stochastic nature and thus indistinguishable from the measurement noise, a protocol based on the use of the random phase multisine is proposed to reveal the accuracy and robustness of the linear OMA technique in the presence of the system nonlinearity. Several frequency- and time-domain based OMA techniques are examined for the modal identification of simulated and real nonlinear mechanical systems. Theoretical analyses are also provided to understand how the system nonlinearity degrades the performance of the OMA algorithms.