Soft-bodied cephalopods such as octopuses are exceptionally intelligent invertebrates with a highly complex nervous system that evolved independently from vertebrates. Because of elevated RNA editing in their nervous tissues, we hypothesized that RNA regulation may play a major role in the cognitive success of this group. We thus profiled messenger RNAs and small RNAs in three cephalopod species including 18 tissues of the Octopus vulgaris. We show that the major RNA innovation of soft-bodied cephalopods is an expansion of the microRNA (miRNA) gene repertoire. These evolutionarily novel miRNAs were primarily expressed in adult neuronal tissues and during the development and had conserved and thus likely functional target sites. The only comparable miRNA expansions happened, notably, in vertebrates. Thus, we propose that miRNAs are intimately linked to the evolution of complex animal brains.