We analyzed sea level data from a set of tide gauge stations located in the central and western Mediterranean Sea, that recorded the tsunami generated by the Mw 6.8 Boumerdès earthquake striking the coast of Algeria on May 21, 2003. This earthquake caused more than 2200 victims and thousands of injured. The causative fault was located a few km offshore and during the rupture a tsunami was triggered. Waves were felt along a large part of the western and northern Mediterranean coasts, and in the Balearic islands waves higher that 2 m were measured. In this paper we analyze a more complete tidal data set, with respect to previous studies, now consisting of 22 tidal stations located in Italy, France and Spain. To characterize the change of the tidal signal at each station we used the Empirical Mode Decomposition (EMD). By means of this technique, which is suitable to analyze and to characterize the dynamical behavior of non-stationary time series, we provide a precise measurement of the arrival times and amplitudes at the tidal stations and identify how this tsunami affected the principal and long term tidal components. Our findings improve previous results for this earthquake, since they allow the detection of significant amplitude fluctuations associated with the tsunami in the majority of stations, including the farthest ones.