Estimations on the influence of evolutionary and ecological forces as drivers of population gene diversity and genetic structure have been performed on a growing number of colonial seabirds, but many remain poorly studied. In particular, the population genetic structure of storm-petrels (Hydrobatidae) has been evaluated in only a few of the 24 recognized species. We assessed the genetic diversity and population structure of the Black Storm-Petrel (Hydrobates melania) and the Least Storm-Petrel (Hydrobates microsoma) in the Gulf of California. The two species were selected because they are pelagic seabirds with comparable ecological traits and breeding grounds. Recent threats such as introduced species of predators and human disturbance have resulted in a decline of many insular vertebrate populations in this region and affected many different aspects of their life histories (ranging from reproductive success to mate selection), with a concomitant loss of genetic diversity. To elucidate to what extent the population genetic structure occurs in H. melania and H. microsoma, we used 719 base pairs from the mitochondrial cytochrome oxidase c subunit I gene. The evaluation of their molecular diversity, genetic structure, and gene flow were performed through diversity indices, analyses of molecular and spatial variance, and isolation by distance (IBD) across sampling sites, respectively. The population genetic structure (via AMOVA and SAMOVA) and isolation by distance (pairwise p-distances and FST/1–FST (using ΦST) were inferred for H. microsoma. However, for H. melania evidence was inconclusive. We discuss explanations leading to divergent population genetic structure signatures in these species, and the consequences for their conservation.