In non-Markovian systems, the current state of the system depends on the full or partial history of its past evolution. Owing to these time correlations, non-Markovian noise violates common assumptions in gate characterization protocols such as randomized benchmarking and gate-set tomography. Here, we perform a case study of the effects of a quantum non-Markovian bath on qubit randomized benchmarking experiments. We consider a model consisting of qubits coupled to a multimode Bosonic bath. We apply unitary operations on the qubits, interspersed with brief interaction with the environment governed by a Hamiltonian. Allowing for non-Markovianity in the interactions leads to clear differences in the randomized benchmarking decay curves in this model, which we analyze in detail. The Markovian model's decay is exponential as expected whereas the model with non-Markovian interactions displays a much slower, almost polynomial, decay. We develop efficient numerical methods for this problem that we use to support our theoretical results. These results inform efforts on incorporating quantum non-Markovian noise in the characterization and benchmarking of quantum devices.