Identifying stably expressed tumor markers that can be used easily to detect cancer is currently an important area of cancer research. By using miRNA microarray, we identified 20 differentially expressed miRNAs in serum samples of breast cancer patients. Expression of miR-125a-5p was relatively lower in patients with shorter survival compared to long-term survivors. In a cohort of breast cancer patients (N = 300), serum expression of miR-125a-5p was negatively and significantly correlated with tumor grade (P = 0.004), lymph-node status (P = 0.004), and tumor size (P < 0.001). Low miR-125a-5p expression was an independent prognostic marker (OR = 0.421; 95% CI = 0.184 to 0.961; P = 0.04) associated with poor survival rates (P = 0.0062). We show that miR-125a-5p directly inhibits expression of the HDAC4 gene, resulting in tumor suppression in vitro and in vivo. Together these results demonstrate that serum miR-125a-5p level in breast cancer may be a useful prognostic biomarker and offer a novel therapeutic avenue by targeting HDAC4 in breast cancer.