This study reconstructs the northern coastline of East Java during the Majapahit period (14th-16th century CE) through an integrated framework combining geomorphological modeling, geospatial analysis, and historical cartographic interpretation. Focusing on the delta systems of the Bengawan Solo and Brantas rivers, the research addresses the longstanding uncertainty regarding the spatial configuration of coastal environments that supported the maritime character of the Majapahit polity. Long-term coastal progradation was quantified using empirical shoreline change data derived from multi-temporal satellite imagery and the Digital Shoreline Analysis System (DSAS). Observed progradation rates in the Bengawan Solo delta (1995-2020) range between 40 and 50 m/year, with localized variability including episodic erosion. To extend this dataset temporally, a segmented historical model was developed, incorporating lower rates during the early post-canalization period (1900-1970: 20-30 m/year), moderate rates during early anthropogenic intensification (1970-1995: 30-40 m/year), and higher rates in the modern period (1995-2025: 40-50 m/year). These calibrated values were applied to the Brantas delta system to derive a representative long-term mean progradation rate of approximately 35 m/year. Based on this model, shoreline displacement was reconstructed over a ~600-year timescale, indicating a cumulative seaward advance of approximately 20-25 km since the 15th century. A simplified relative sea-level framework was incorporated as a secondary boundary condition, demonstrating that sediment-driven vertical accretion substantially exceeds plausible sea-level rise, thereby supporting sustained delta emergence and lateral expansion. The reconstructed paleogeography suggests that large portions of present-day inland regions, including Gresik, Surabaya, Lamongan, and Sidoarjo, were likely situated within coastal or estuarine environments during the Majapahit era. This interpretation is consistent with early modern cartographic evidence, including the works of João Baptista Lavanha (1615) and Thomas Stamford Raffles (1817), as well as modern land use and land cover datasets derived from the Indonesian RBI mapping system. This study proposes a probabilistic spatial framework that bridges geomorphology and historiography. The results highlight a sediment-dominated deltaic system capable of reshaping coastal landscapes over centennial timescales, providing a new basis for interpreting historical settlement patterns and guiding future archaeological exploration in northern Java.