The sea cucumber, an important economic species, has encountered high mortality since 2013 in northern China because of seasonal environmental stress such as hypoxia, high temperature, and low salinity. MicroRNAs (miRNAs) are important in regulating gene expression in marine organisms in response to environmental change. In this study, high-throughput sequencing was used to investigate alterations in miRNA expression in the sea cucumber under different levels of dissolved oxygen (DO). Nine small RNA libraries were constructed from the sea cucumber respiratory trees. A total of 26 differentially expressed miRNAs, including 12 upregulated and 14 downregulated miRNAs, were observed in severe hypoxia (DO 2 mg/L) compared with mild hypoxia (DO 4 mg/L) and normoxic conditions (DO 8 mg/L). Twelve differentially expressed miRNAs were clustered in severe hypoxia. In addition, real-time PCR revealed that 14 randomly selected differentially expressed miRNAs showed significantly increased expressions in severe hypoxia and the expressions of nine miRNAs, including key miRNAs such as Aja-miR-1, Aja-miR-2008, and Aja-miR-184, were consistent with the sequencing results. Moreover, gene ontology and pathway analyses of putative target genes suggest that these miRNAs are important in redox, transport, transcription, and hydrolysis under hypoxia stress. Notably, novel-miR-1, novel-miR-2, and novel-miR-3 were specifically clustered and upregulated in severe hypoxia, which may provide new insights into novel "hypoxamiR" identification. These results will provide a basis for future studies of miRNA regulation and molecular adaptive mechanisms in sea cucumbers under hypoxia stress.