The wide prevalence and regulated expression of long non-coding RNAs (lncRNAs) highlight their functional roles, but the molecular basis for their activity and structure-function relationships remain to be investigated, with few exceptions. Among the relatively few lncRNAs conserved over significant evolutionary distances is the long intergenic non-coding RNA (lincRNA) Cyrano (orthologous to human OIP5-AS1), which contains a region of 300 highly conserved nucleotides within tetrapods, which in turn contains a functional stretch of 26 nucleotides of deep conservation. This region binds to and facilitates the degradation of the microRNA miR-7, a short ncRNA with multiple cellular functions, including modulation of oncogenic expression. We probed the secondary structure of Cyrano in vitro and in cells using chemical and enzymatic probing, and validated the results using comparative sequence analysis. At the center of the functional core of Cyrano is a cloverleaf structure maintained over the >400 million years of divergent evolution that separate fish and primates. This strikingly conserved motif provides interaction sites for several RNA-binding proteins and masks a conserved recognition site for miR-7. Conservation in this region strongly suggests that the function of Cyrano depends on the formation of this RNA structure, which could modulate the rate and efficiency of degradation of miR-7.