There is a critical need to identify molecular markers that can reliably aid in stratifying esophageal adenocarcinoma (EAC) risk in patients with Barrett's esophagus. MicroRNAs (miRNA/miR) are one such class of biomolecules. In the present cross-sectional study, we characterized miRNA alterations in progressive stages of neoplastic development, i.e., metaplasia–dysplasia–adenocarcinoma, with an aim to identify candidate miRNAs potentially associated with progression. Using next generation sequencing (NGS) as an agnostic discovery platform, followed by quantitative real-time PCR (qPCR) validation in a total of 20 EACs, we identified 26 miRNAs that are highly and frequently deregulated in EACs (≥4-fold in >50% of cases) when compared to paired normal esophageal squamous (nSQ) tissue. We then assessed the 26 EAC-derived miRNAs in laser microdissected biopsy pairs of Barrett's metaplasia (BM)/nSQ (n = 15), and high-grade dysplasia (HGD)/nSQ (n = 14) by qPCR, to map the timing of deregulation during progression from BM to HGD and to EAC. We found that 23 of the 26 candidate miRNAs were deregulated at the earliest step, BM, and therefore noninformative as molecular markers of progression. Two miRNAs, miR-31 and –31*, however, showed frequent downregulation only in HGD and EAC cases suggesting association with transition from BM to HGD. A third miRNA, miR-375, showed marked downregulation exclusively in EACs and in none of the BM or HGD lesions, suggesting its association with progression to invasive carcinoma. Taken together, we propose miR-31 and –375 as novel candidate microRNAs specifically associated with early- and late-stage malignant progression, respectively, in Barrett's esophagus.