Because a change in the natural frequencies of a structure indicates structural health problems, monitoring the natural frequencies crucial. Long-term measurement for the Uldolmok tidal current power plant structure has shown that its natural frequencies fluctuate with a constant cycle twice a day. In this study, lab-scale tests to investigate the causes of these natural frequency fluctuations were carried out in a circulating water channel. Three independent variables in the tests that could affect the fluctuation of the natural frequencies were the water level, current velocity, and boundary condition between the specimen and the bottom of the circulating water channel. The experimental results were verified with numerical ones using ABAQUS. It was found that the fluctuation of the natural frequencies was governed by a decrease in stiffness due to the boundary condition much more than the effect of added mass. In addition, it was found that the natural frequency would decrease with an increase in the tidal current velocity because of its nonlinearity when the boundary condition was severely deteriorated due to damage.