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.