An algorithm for modeling the evolution of the regulatory signals involving the interaction with RNA secondary structure is proposed. The algorithm implies that the species phylogenetic tree is known and is based on the assumption that the considered signals have a conserved secondary structure. The input data are the extant primary structure of a signal for all leaves of the phylogenetic tree; the algorithm computes the signal primary and secondary structures at all the nodes. Concurrently, the algorithm constructs a multiple alignment of the extant (in leaves) sites of a regulatory signal taking into account its secondary structure. The results of successful testing of the algorithm for three main types of attenuation regulation in bacteria—classic attenuation (threonine and leucine biosyntheses in Gammaproteobacteria), T-box (in Actinobacteria), and RFN-mediated (in Eubacteria) regulations—are described.