Interaction of fluid forces with flexible structures is often prone to dynamical instabilities, such as aeroelastic flutter. The onset of this instability is marked by sustained large amplitude oscillations and is detrimental to the structure's integrity. Therefore, investigating the possible physical mechanisms behind the onset of flutter instability has attracted considerable attention within the aeroelastic community. Recent studies have shown that in the presence of oncoming fluctuating flows, the onset of flutter instability is presaged by an intermediate regime of oscillations called intermittency. Further, based on the intensity of flow fluctuations and the relative time scales present in the flow, qualitatively different types of intermittency at different flow regimes have been reported hitherto. However, the coupled interaction between the pitch (torsion) and plunge (bending) modes during the transition to aeroelastic flutter has not been explored. With this, we demonstrate with a mathematical model that the onset of flutter instability under randomly fluctuating flows occurs via a mutual phase synchronization between the pitch and the plunge modes. We show that at very low values of mean flow speeds, the response is by and large noisy and, consequently, a phase asynchrony between the modes is present. Interestingly, during the regime of intermittency, we observe the coexistence of patches of synchronized periodic bursts interspersed amidst a state of desynchrony between the pitch and the plunge modes. On the other hand, at the onset of flutter, we observe a complete phase synchronization between the pitch and plunge modes. This study concludes by utilizing phase locking value as a quantitative measure to demarcate different states of synchronization in the aeroelastic response. © 2019 Author(s).