We study the open dynamics of a quantum two-level system coupled to an environment modeled by random matrices. Using the quantum channel formalism, we investigate different quantum Markovianity measures and criteria. A thorough analysis of the whole parameter space, reveals a wide range of different regimes, ranging from strongly non-Markovian to Markovian dynamics. In contrast to analytical models, all non-Markovianity measures and criteria have to be applied to data with fluctuations and statistical uncertainties. We discuss the practical usefulness of the different approaches.