Populations carry a genetic signal of their demographic past, providing an opportunity for investigating the processes that shaped their evolution. Our ability to infer population histories can be enhanced by including ancient DNA data. Using serial-coalescent simulations and a range of both quantitative and temporal sampling schemes, we test the power of ancient mitochondrial sequences and nuclear single-nucleotide polymorphisms (SNPs) to detect past population bottlenecks. Within our simulated framework, mitochondrial sequences have only limited power to detect subtle bottlenecks and/or fast post-bottleneck recoveries. In contrast, nuclear SNPs can detect bottlenecks followed by rapid recovery, although bottlenecks involving reduction of less than half the population are generally detected with low power unless extensive genetic information from ancient individuals is available. Our results provide useful guidelines for scaling sampling schemes and for optimizing our ability to infer past population dynamics. In addition, our results suggest that many ancient DNA studies may face power issues in detecting moderate demographic collapses and/or highly dynamic demographic shifts when based solely on mitochondrial information.