Empirical studies have uncovered significant evidence for selection in natural populations, but a rigorous characterization of these selection pressures has been difficult. The main reason for this gap is the lack of theoretical predictions for the distortion in genealogies caused by selection, except in a few restricted scenarios: when all mutations are either weakly selected, or have a single effect size. In reality, mutational effects often span several orders of magnitude, but it is impossible to account for this in current theoretical models. In these circumstances, selection leads to correlations between the mutational and genealogical processes that cannot be accounted for by analogy with a population with a stable geographic structure. We describe a new coalescent framework that naturally accounts for these correlations by grouping individuals with the same nonsynonymous mutations into genotypes and considering the dynamics of these genotypes first. We show how our approach naturally extends to purifying selection due to a broad range of fitness effects and predicts patterns of neutral variation. This scheme is significantly more accurate than existing theoretical methods based on reductions in the effective population size and significantly more efficient than the alternative of whole-chromosome simulations. In particular, we show that, in certain scenarios, the genetic diversity of a population steadily declines as the size of the population increases, in contrast to predictions from the background selection limit. We give quantitative predictions for the distortions in the genealogies and patterns of genetic diversity depend on the size of the population, mutation rate and the full distribution of selective effects. Our results have important practical implications for the interpretation of natural sequence variability and the characterization of selective pressures in natural populations.