The long-term history of the Earth-Moon system as reconstructed from the geological record remains unclear when based on fossil growth bands and tidal laminations. A possibly more robust method is provided by the sedimentary record of Milankovitch cycles (climatic precession, obliquity, and orbital eccentricity), whose relative ratios in periodicity change over time as a function of a decreasing Earth spin rate and increasing lunar distance. However, for the critical older portion of Earth's history where information on Earth-Moon dynamics is sparse, suitable sedimentary successions in which these cycles are recorded remain largely unknown, leaving this method unexplored. Here we present results of cyclostratigraphic analysis and high-precision U-Pb zircon dating of the lower Paleoproterozoic Joffre Member of the Brockman Iron Formation, NW Australia, providing evidence for Milankovitch forcing of regular lithological alternations related to Earth's climatic precession and orbital eccentricity cycles. Combining visual and statistical tools to determine their hierarchical relation, we estimate an astronomical precession frequency of 108.6 ± 8.5 arcsec/y, corresponding to an Earth-Moon distance of 321,800 ± 6,500 km and a daylength of 16.9 ± 0.2 h at 2.46 Ga. With this robust cyclostratigraphic approach, we extend the oldest reliable datum for the lunar recession history by more than 1 billion years and provide a critical reference point for future modeling and geological investigation of Precambrian Earth-Moon system evolution.