We analyze the impact of non-Markovian classical noise on single-qubit randomized benchmarking experiments, in a manner that explicitly models the realization of each gate via realistic finite-duration pulses. Our new framework exploits the random nature of each gate sequence to derive expressions for the full survival probability decay curve which are non-perturbative in the noise strength. In the presence of non-Markovian noise, our approach shows that the decay curve can exhibit a strong dependence on the implementation method, with regimes of both exponential and power law decays. We discuss how these effects can complicate the interpretation of a randomized-benchmarking experiment, but also how to leverage them to probe non-Markovianty.