We derive exact results for the spectral density S(omega) of the output of the Preisach model, a standard model for complex, nonlocal hysteresis. We obtain general results for uncorrelated input signals with arbitrary input and Preisach densities. It is shown analytically that uncorrelated input signals are transformed into output exhibiting long-time correlations. For the simplest example of uniform input and Preisach distributions we prove that correlations decay asymptotically with a t(-3) power law corresponding to a logarithmic low frequency divergence of the second derivative of the spectrum S(omega) . A simpler expression for symmetric Preisach models is also obtained, which is discussed in detail in Part II, showing that long-time tails or even 1/f noise are general features of this class of models.