Inferring and understanding changes in effective population size over time is a major challenge for population genetics. Here we investigate some theoretical properties of random mating populations with varying size over time. In particular, we present an exact method to compute the population size as a function of time using the distributions of coalescent-times of samples of any size. This result reduces the problem of population size inference to a problem of estimating coalescent-time distributions. Using tree inference algorithms and genetic data, we can investigate the effects of a range of conditions associated with real data, for instance finite number of loci, sample size, mutation rate and presence of cryptic recombination. We show that our method requires at least a modest number of loci (10,000 or more) and that increasing the sample size from 2 to 10 greatly improves the inference whereas further increase in sample size only results in a modest improvement, even under as scenario of exponential growth. We also show that small amounts of recombination can lead to biased population size reconstruction when unaccounted for. The approach can handle large sample sizes and the computations are fast. We apply our method on human genomes from 4 populations and reconstruct population size profiles that are coherent with previous knowledge, including the Out-of-Africa bottleneck. Additionally, a potential difference in population size between African and non-African populations as early as 400 thousand years ago is uncovered.