Increasing evidence suggests small non-coding RNAs (ncRNAs) such as microRNAs (miRNAs) control levels of mRNA expression during experience-related remodelling of the brain. Here we use an associative olfactory learning paradigm in the honeybee Apis mellifera to examine gene expression changes in the brain during memory formation. Brain transcriptome analysis reveals a general downregulation of protein-coding genes, including asparagine synthetase and actin, and upregulation of ncRNAs. miRNA-mRNA network predictions together with PCR validation suggest miRNAs including miR-210 and miR-932 target the downregulated protein-coding genes. Feeding cholesterol-conjugated antisense RNA to bees results in the inhibition of miR-210 and of miR-932. Loss of miR-932 impairs long-term memory formation, but not memory acquisition. Functional analyses show that miR-932 interacts with Act5C, providing evidence for direct regulation of actin expression by an miRNA. An activity-dependent increase in miR-932 expression may therefore control actin-related plasticity mechanisms and affect memory formation in the brain.