The phenomenological linear response theory of non-Markovian stochastic resonance (SR) is put forward for stationary two-state renewal processes. In terms of a derivation of a non-Markov regression theorem we evaluate the characteristic SR-quantifiers; i.e., the spectral power amplification (SPA) and the signal-to-noise ratio (SNR), respectively. In clear contrast to Markovian-SR, a characteristic benchmark of genuine non-Markovian SR is its distinctive dependence of the SPA and SNR on small (adiabatic) driving frequencies; particularly, the adiabatic SNR becomes strongly suppressed over its Markovian counterpart. This non-Markovian SR-theory is elucidated for a fractal gating dynamics of a potassium ion channel possessing an infinite variance of closed sojourn times.