A cytidine-free ribozyme with RNA ligase activity was obtained by in vitro evolution, starting from a pool of random-sequence RNAs that contained only guanosine, adenosine, and uridine. This ribozyme contains 74 nt and catalyzes formation of a 3′,5′-phosphodiester linkage with a catalytic rate of 0.016 min−1. The RNA adopts a simple secondary structure based on a three-way junction motif, with ligation occurring at the end of a stem region located several nucleotides away from the junction. Cytidine was introduced to the cytidine-free ribozyme in a combinatorial fashion and additional rounds of in vitro evolution were carried out to allow the molecule to adapt to this added component. The resulting cytidine-containing ribozyme formed a 3′,5′ linkage with a catalytic rate of 0.32 min−1. The improved rate of the cytidine-containing ribozyme was the result of 12 mutations, including seven added cytidines, that remodeled the internal bulge loops located adjacent to the three-way junction and stabilized the peripheral stem regions.