Mitochondrial and nuclear sequence data should recover historical demographic events at different temporal scales due to differences in their effective population sizes and substitution rates. This expectation was tested for two closely related coral reef fish, the tube blennies Acanthemblemaria aspera and A. spinosa. These two have similar life histories and dispersal potentials, and co-occur throughout the Caribbean. Sequence data for one mitochondrial and two nuclear markers were collected for 168 individuals across the species' Caribbean ranges. While both species shared a similar pattern of genetic subdivision, A. spinosa had 20-25-times greater nucleotide sequence divergence among populations than A. aspera at all three markers. Substitution rates estimated using a relaxed clock approach revealed that mitochondrial COI is evolving at 11.2% pairwise sequence divergence per million years. This rapid mitochondrial rate had obscured the signal of old population expansions for both species, which were only recovered using the more slowly evolving nuclear markers. However, the rapid COI rate allowed the recovery of a recent expansion in A. aspera corresponding to a period of increased habitat availability. Only by combining both nuclear and mitochondrial data were we able to recover the complex demographic history of these fishes.