We have developed a hidden Markov model and optimization procedure for photon-based single-molecule FRET data, which takes into account the trace-dependent background intensities. This analysis technique reveals an unprecedented amount of detail in the folding kinetics of the Diels-Alderase ribozyme. We find a multitude of extended (low-FRET) and compact (high-FRET) states. Five states were consistently and independently found in two FRET constructs and three Mg2+ concentrations. Structures generally tend to become more compact upon addition of Mg2+. Some compact structures are found to significantly depend on Mg2+ concentration, suggesting a tertiary fold stabilized by Mg2+ ions. One compact structure was found to be Mg2+-independent, consistent with stabilization by tertiary Watson-Crick base pairing found in the folded Diels-Alderase structure. A hierarchy of timescales was found, including dynamics of 10 ms or faster, likely due to tertiary structure fluctuations, and slow dynamics on the seconds timescale, presumably associated with significant changes in secondary structure. The folding pathways proceed through a series of intermediate secondary structures. There exist both, compact pathways and more complex ones, which display tertiary unfolding, then secondary refolding and, subsequently, again tertiary refolding.