Patagonicola Packer new genus is described for two species of xeromelissine bee (Hymenoptera: Colletidae) from Patagonian Argentina. One species, P. graveli Packer new species is described; the second species, P. aenigma (Packer) new combination, originally placed in Chilicola Spinola, 1851 subgenus Chilioediscelis Toro and Moldenke, 1979, is designated as the type species. The new genus is superficially most similar to Xenochilicola Toro and Moldenke, 1979 but possesses none of the derived characteristics that were originally used to define that genus. Results of a phylogenetic analysis, based upon 114 morphological characters, are presented and suggest that the new genus is the sister clade to (Geodiscelis Michener and Rozen, 1999 + Xeromelissa Cockerell, 1926). An illustrated key is provided for the genera of Xeromelissinae and for the two species of Patagonicola.