This paper shows the potential of excitation-emission fluorescence spectroscopy (EEFS) and three-way methods of analysis [parallel factor analysis (PARAFAC) and multiway partial least-squares (N-PLS) regression] as a complementary technique for olive oil characterization. The fluorescence excitation-emission matrices of a set of Spanish extra virgin, virgin, pure, and olive pomace oils were measured, and the relationship between them and some of the quality parameters of olive oils (peroxide value, K232, and K270) was studied. N-PLS was found to be more suitable than PARAFAC combined with multiple linear regression for correlating fluorescence and quality parameters, yielding better fits and lower prediction errors. The best results were obtained for predicting K270. EEFS allowed detection of extra virgin olive oils highly degraded at early stages (with high peroxide value) and little oxidized pure olive oils (with low K270). The proposed methodology may be used as an aid to analyze doubtful samples.