The regulation of mitochondrial proteome is unique in that its components have origins in both mitochondria and nucleus. With the development of OMICS technologies, emerging evidence indicates an interaction between mitochondria and nucleus based not only on the proteins but also on the non-coding RNAs (ncRNAs). It is now accepted that large parts of the non-coding genome are transcribed into various ncRNA species. Although their characterization has been a hot topic in recent years, the function of the majority remains unknown. Recently, ncRNA species microRNA (miRNA) and long-non coding RNAs (lncRNA) have been gaining attention as direct or indirect modulators of the mitochondrial proteome homeostasis. These ncRNA can impact mitochondria indirectly by affecting transcripts encoding for mitochondrial proteins in the cytoplasm. Furthermore, reports of mitochondria-localized miRNAs, termed mitomiRs, and lncRNAs directly regulating mitochondrial gene expression suggest the import of RNA to mitochondria, but also transcription from the mitochondrial genome. Interestingly, ncRNAs have been also shown to hide small open reading frames (sORFs) encoding for small functional peptides termed micropeptides, with several examples reported with a role in mitochondria. In this review, we provide a literature overview on ncRNAs and micropeptides found to be associated with mitochondrial biology in the context of both health and disease. Although reported, small study overlap and rare replications by other groups make the presence, transport, and role of ncRNA in mitochondria an attractive, but still challenging subject. Finally, we touch the topic of their potential as prognosis markers and therapeutic targets.