Nonextensive statistical mechanics, pioneered by Tsallis, has recently achieved a generalization of the Gutenberg-Richter law for earthquakes. This remarkable generalization is combined here with natural time analysis, which enables the distinction of two origins of self-similarity, i.e., the process' memory and the process' increments infinite variance. By using also detrended fluctuation analysis for the detection of long-range temporal correlations, we demonstrate the existence of both temporal and magnitude correlations in real seismic data of California and Japan. Natural time analysis reveals that the nonextensivity parameter q , in contrast to some published claims, cannot be considered as a measure of temporal organization, but the Tsallis formulation does achieve a satisfactory description of real seismic data for Japan for q=1.66 when supplemented by long-range temporal correlations.