Over the course of its motion through the Galaxy, our solar system has encountered many interstellar environments of varying characteristics. Interstellar medium (ISM) density variations spanning seven orders of magnitude are commonly seen throughout the general Galactic environment, and a sufficiently dense cloud within this range has the potential to dramatically alter the structure of the heliosphere. We present observations of the ISM environments the Sun has most recently encountered based on high-resolution optical spectra toward nearby stars in the direction of the historical solar trajectory. The data were obtained with the highest-resolution spectrographs available, including the Tull Spectrograph on the Harlan J. Smith Telescope at McDonald Observatory and the Ultra-High-Resolution Facility on the Anglo-Australian Telescope at the Anglo-Australian Observatory. Observations were made of interstellar Na I and Ca II doublet absorption toward 43 bright stars within about 500 pc. No absorption is seen out to a distance of 120 pc (consistent with the outer boundary of the Local Bubble), but a complex collection of absorbers is seen in stars beyond 120 pc. While common absorbers are consistently seen in most sight lines, significant spatial variation is also detected, even between closely spaced sight lines. This pervasive evidence of small-scale structure not only speaks to the complexity of the morphology or physical properties of the gas in the ISM, but also emphasizes that dramatic structural changes to the heliosphere are common and it is important to understand the implications of such changes, such as the modulation in the cosmic ray flux, on planets.