The historical records of the low- and high-water levels of the Nile River are among the longest climatic records that have near-annual resolution. There are few gaps in the first part of the records (A.D. 622–1470) and larger gaps later (A.D. 1471–1922). We apply advanced spectral methods, Singular-Spectrum Analysis (SSA) and the Multi-Taper Method (MTM), to fill the gaps and to locate interannual and interdecadal periodicities. The gap filling uses a novel, iterative version of SSA. Our analysis reveals several statistically significant features of the records: a nonlinear, data-adaptive trend that includes a 256-year cycle, a quasi-quadriennial (4.2-year) and a quasi-biennial (2.2-year) mode, as well as additional periodicities of 64, 19, 12, and, most strikingly, 7 years. The quasi-quadriennial and quasi-biennial modes support the long-established connection between the Nile River discharge and the El-Niño/Southern Oscillation (ENSO) phenomenon in the Indo-Pacific Ocean. The longest periods might be of astronomical origin. The 7-year periodicity, possibly related to the biblical cycle of lean and fat years, seems to be due to North Atlantic influences.