MicroRNAs (miRNAs) and endogenous small interfering RNAs (siRNAs) are key players in plant stress responses. Here, we present the sRNA transcriptomes of mangroves Bruguiera gymnorrhiza and Kandelia candel. Comparative computational analyses and target predictions revealed that mangroves exhibit distinct sRNA regulatory networks that differ from those of glycophytes. A total of 32 known and three novel miRNA families were identified. Conserved and mangrove-specific miRNA targets were predicted; the latter were widely involved in stress responses. The known miRNAs showed differential expression between the mangroves and glycophytes, reminiscent of the adaptive stress-responsive changes in Arabidopsis. B. gymnorrhiza possessed highly abundant but less conserved TAS3 trans-acting siRNAs (tasiRNAs) in addition to tasiR-ARFs, with expanded potential targets. Our results indicate that the evolutionary alteration of sRNA expression levels and the rewiring of sRNA-regulatory networks are important mechanisms underlying stress adaptation. We also identified sRNAs that are involved in salt and/or drought tolerance and nutrient homeostasis as possible contributors to mangrove success in stressful environments.