Tidal rhythmites are small-scale sedimentary structures that can preserve a hierarchy of astronomically induced tidal periods. They can also preserve a record of periodic nontidal sedimentation. If properly interpreted and understood, tidal rhythmites can be an important component of paleoastronomy and can be used to extract information on ancient lunar orbital dynamics including changes in Earth-Moon distance through geologic time. Herein we present techniques that can be used to calculate ancient Earth-Moon distances. Each of these techniques, when used on a modern high-tide data set, results in calculated estimates of lunar orbital periods and an Earth-Moon distance that fall well within 1 percent of the actual values. Comparisons to results from modern tidal data indicate that ancient tidal rhythmite data as short as 4 months can provide suitable estimates of lunar orbital periods if these tidal records are complete. An understanding of basic tidal theory allows for the evaluation of completeness of the ancient tidal record as derived from an analysis of tidal rhythmites. Utilizing the techniques presented herein, it appears from the rock record that lunar orbital retreat slowed sometime during the mid-Paleozoic.