Tertiary stabilizing motifs (TSMs) between terminal loops or internal bulges facilitate folding of natural hammerhead ribozymes (hRz) under physiological conditions. However, both substrate and enzyme strands contribute nucleotides to the TSMs of trans-cleaving hRz, complicating the design of hRz that exploit TSMs to target specific mRNA. To overcome this limitation, we used SELEX to identify new, artificial TSMs that are less sensitive to sequence context. Nucleotides in loop II or in a bulge within the ribozyme strand of stem I were randomized, while the interaction partner was held constant. All nucleotides of the substrate pair with the ribozyme, minimizing their possible recruitment into the TSM, as such recruitment could constrain choice of candidate target sequences. Six cycles of selection identified cis-acting ribozymes that were active in 100 μM MgCl2. The selected motifs partially recapitulate TSMs found in natural hRz, suggesting that the natural motifs are close to optimal for their respective contexts. Ribozyme “RzB” showed enhanced thermal stability by retaining trans-cleavage activity at 80°C in 10 mM MgCl2 and at 70°C in 2 mM MgCl2. A variant of ribozyme “RzB” with a continuously paired stem 1 rapidly lost activity as temperature was increased. The selected motifs are modular, in that they permit trans-cleavage of several substrates in submillimolar MgCl2, including two substrates derived from the U5 genomic region of HIV-1. The new, artificial tertiary stabilized hRz are thus nearly independent of sequence context and enable for the first time the use of highly active hRz targeting almost any mRNA at physiologically relevant magnesium concentrations.