Long non-protein coding RNAs (lncRNAs) represent the most diverse class of genetic elements in metazoan genomes, both in terms of their structure and function, which complicates their systematic functional characterization. The formation of secondary and tertiary structures is a hallmark of functional non-coding RNAs. However, evaluating the prevalence and evolutionary conservation (a hallmark of function) of these structural features in lncRNAs is a significantly complex and noisy task. We benchmarked the performance of RNALalifold–a dynamic window consensus structure folding algorithm–with two statistical strategies (SISSIz & R-scape) on detecting conserved 2D structures using both mitochondrial genome alignments and Rfam entries pasted into shuffled genomic alignments. Calibrated settings were then used to scan genomic alignments of 46 mammalian genomes, revealing 2.8 million evolutionarily conserved structure (ECS) predictions. Reinforcing the functional significance of these regions, ECS are significantly enriched in clinically-relevant single nucleotide variants. A subset of the ECS-associated alignments were used to construct covariance models and scan the human genome for homology, revealing millions of additional loci. Interestingly, some ECS-homologs were found in both repetitive and non-repetitive sequences, exposing potential evidence for viral mimicry or functional exaptation of putative regulatory motifs in mobile genetic elements. These findings suggest the presence of both negative and positive selection dynamics on RNA domains, offering a rich resource for the functional annotation of lncRNAs, as well as unprecedented insights into the regulatory architecture of mammalian genomes.