The structure of the heliosphere is investigated for a period when the Sun enters a cold dense unmagnetized interstellar cloud. Under these conditions the heliospheric interface resembles the two-shock standard model with the termination shock located close to 23 AU in the upwind direction. Anomalous and galactic cosmic ray fluxes are calculated and compared with their present day intensities in the inner heliosphere. A tenfold increase in anomalous cosmic ray and a twofold increase in galactic cosmic ray intensities are possible if heliosheath modulation is reduced, in this high-density case. On the basis of our heliospheric modeling, we show that a possible explanation of the enhancement of cosmogenic elements in ice and sediment samples 35,000 and 60,000 years BP might be an encounter of the Sun with a dense interstellar cloud.