microRNAs (miRNAs) repress target transcripts through partial complementarity. By contrast, highly complementary miRNA-binding sites within viral and artificially engineered transcripts induce miRNA degradation in vitro and in cell lines. Here, we show that a genome-encoded transcript harboring a near-perfect and deeply conserved miRNA-binding site for miR-29 controls zebrafish and mouse behavior. This transcript originated in basal vertebrates as a long noncoding RNA (lncRNA) and evolved to the protein-coding gene NREP in mammals, where the miR-29-binding site is located within the 3′ UTR. We show that the near-perfect miRNA site selectively triggers miR-29b destabilization through 3′ trimming and restricts its spatial expression in the cerebellum. Genetic disruption of the miR-29 site within mouse Nrep results in ectopic expression of cerebellar miR-29b and impaired coordination and motor learning. Thus, we demonstrate an endogenous target-RNA-directed miRNA degradation event and its requirement for animal behavior.