MicroRNAs (miRNAs) are non-coding RNAs of ~22 nucleotides in length that regulate gene expression by interfering with the stability and translation of mRNAs. Their expression is regulated during development, under a wide variety of stress conditions and in several pathological processes. In nature, animals often face feast or famine conditions. We observed that subjecting early L4 larvae from Caenorhabditis elegans to a 12-hr starvation period produced worms that are thinner and shorter than well-fed animals, with a decreased lipid accumulation, diminished progeny, reduced gonad size, and an increased lifespan. Our objective was to identify which of the 302 known miRNAs of C. elegans changed their expression under starvation conditions as compared to well-fed worms by means of deep sequencing in early L4 larvae. Our results indicate that 13 miRNAs (miR-34-3p, the family of miR-35-3p to miR-41-3p, miR-39-5p, miR-41-5p, miR-240-5p, miR-246-3p and miR-4813-5p) were upregulated, while 2 miRNAs (let-7-3p and miR-85-5p) were downregulated in 12-hr starved vs. well-fed early L4 larvae. Some of the predicted targets of the miRNAs that changed their expression in starvation conditions are involved in metabolic or developmental process. In particular, miRNAs of the miR-35 family were upregulated 6–20 fold upon starvation. Additionally, we showed that the expression of gld-1, important in oogenesis, a validated target of miR-35-3p, was downregulated when the expression of miR-35-3p was upregulated. The expression of another reported target, the cell cycle regulator lin-23, was unchanged during starvation. This study represents a starting point for a more comprehensive understanding of the role of miRNAs during starvation in C. elegans.