We show how to incorporate fluctuations of the recombination rate along the chromosome into standard gene-genealogical models for the decorrelation of gene histories. This enables us to determine how small-scale fluctuations (Poissonian hot-spot model) and large-scale variations (Kong et al. 2002) of the recombination rate influence this decorrelation. We find that the empirically determined large-scale variations of the recombination rate give rise to a significantly slower decay of correlations compared to the standard, unstructured gene-genealogical model assuming constant recombination rate. A model with long-range recombination-rate variations and with demographic structure (divergent population) is found to be consistent with the empirically observed slow decorrelation of gene histories. Conversely, we show that small-scale recombination-rate fluctuations do not alter the large-scale decorrelation of gene histories.