Structures such as turbomachinery blades, industrial fans, propellers, etc. can be modeled as twisted beams. The study of dynamics of these structures is vital as operational failure of such structures can have catastrophic consequences. As the inclusion of twist and rotation complicates the problem, Finite Element (FE) method is widely used to determine the modal characteristics of rotating twisted beams. In this work, a novel formula is derived to estimate the natural frequencies of rotating twisted beams. The formula is derived using the perturbation method. The twist angle and the rotating speed are treated as the perturbation parameters. In general, the dynamics of rotating twisted beams is coupled in the two transverse planes. However, in the first part of the work the problem is assumed to be uncoupled and it is shown that this assumption is valid under certain cases. In the second part, the problem of general coupled dynamics is solved. Interesting insights based on the formula are presented. The accuracy of the derived formula is verified by comparing it with the literature and FE simulation results. It has been shown that the formula is valid over a fairly large range of twist angles and rotating speeds. In contrast to the detailed FE simulation, the derived analytical formula will be better suited for design iterations in industrial practice. © 2020, Springer Nature B.V.