Recent molecular phylogenetic studies have greatly improved our understanding of the higher classification of the bee genus Andrena Fabricius. Based on these findings, we herein describe three new, early-diverging western Palaearctic subgenera of the genus: Andrena (Warnckandrena) Pisanty subgen. nov., A. (Uncandrena) Pisanty subgen. nov., and A. (Vellandrena) Pisanty subgen. nov. For each subgenus, we provide a detailed description and a diagnosis against its closest morphological relatives, as well as information on flower hosts and pollen preferences. The following new species are described: Andrena (Warnckandrena) otoolei Pisanty sp. nov. from Turkey and the Levant, A. (Warnckandrena) papio Pisanty sp. nov. from Turkey, and A. (incertae sedis) remota Wood sp. nov. from China. The female of A. (Vellandrena) bassana Warncke, 1969 is described for the first time. The formerly infraspecific name Andrena (Vellandrena) etesiaca Warnkce, 1975 stat. nov. is recognized as a valid species. We additionally briefly review the enigmatic subgenus A. (Melittoides) Friese, 1921, and designate a lectotype for A. (Melittoides) melittoides Friese, 1899. We discuss main ancestral traits and evolutionary patterns that may be inferred with our improved concept of the genus. This study is another important step in the enormous project of revising the systematics of the gigantic genus Andrena.