It has been recently shown [N. V. Sarlis, Phys. Rev. E 84, 022101 (2011) and N. V. Sarlis and S.-R. G. Christopoulos, Chaos 22, 023123 (2012)] that earthquakes of magnitude M greater or equal to 7 are globally correlated. Such correlations were identified by studying the variance κ 1 of natural time which has been proposed as an order parameter for seismicity. Here, we study the fluctuations of this order parameter using the Global Centroid Moment Tensor catalog for a magnitude threshold Mthres = 5.0 and focus on its behavior before major earthquakes. Natural time analysis reveals that distinct minima of the fluctuations of the order parameter of seismicity appear within almost five and a half months on average before all major earthquakes of magnitude larger than 8.4. This phenomenon corroborates the recent finding [N. V. Sarlis et al., Proc. Natl. Acad. Sci. U.S.A. 110, 13734 (2013)] that similar minima of the seismicity order parameter fluctuations had preceded all major shallow earthquakes in Japan. Moreover, on the basis of these minima a statistically significant binary prediction method for earthquakes of magnitude larger than 8.4 with hit rate 100% and false alarm rate 6.67% is suggested.