Beneficial mutations drive adaptive evolution, yet their selective advantage does not ensure their fixation. Haldane's application of single-type branching process theory showed that genetic drift alone could cause the extinction of newly arising beneficial mutations with high probability. With linkage, deleterious mutations will affect the dynamics of beneficial mutations and might further increase their extinction probability. Here, we model the lineage dynamics of a newly arising beneficial mutation as a multitype branching process. Our approach accounts for the combined effects of drift and the stochastic accumulation of linked deleterious mutations, which we call lineage contamination We first study the lineage-contamination phenomenon in isolation, deriving dynamics and survival probabilities (the complement of extinction probabilities) of beneficial lineages. We find that survival probability is zero when [Formula: see text] where U is deleterious mutation rate and [Formula: see text] is the selective advantage of the beneficial mutation in question, and is otherwise depressed below classical predictions by a factor bounded from below by [Formula: see text] We then put the lineage contamination phenomenon into the context of an evolving population by incorporating the effects of background selection. We find that, under the combined effects of lineage contamination and background selection, ensemble survival probability is never zero but is depressed below classical predictions by a factor bounded from below by [Formula: see text] where [Formula: see text] is mean selective advantage of beneficial mutations, and [Formula: see text] This factor, and other bounds derived from it, are independent of the fitness effects of deleterious mutations. At high enough mutation rates, lineage contamination can depress fixation probabilities to values that approach zero. This fact suggests that high mutation rates can, perhaps paradoxically, (1) alleviate competition among beneficial mutations, or (2) potentially even shut down the adaptive process. We derive critical mutation rates above which these two events become likely.