Domestic cattle were brought to Spain by early settlers and agricultural societies. Due to missing Neolithic sites in the Spanish region of Galicia, very little is known about this process in this region. We sampled 18 cattle subfossils from different ages and different mountain caves in Galicia, of which 11 were subject to sequencing of the mitochondrial genome and phylogenetic analysis, to provide insight into the introduction of cattle to this region. We detected high similarity between samples from different time periods and were able to compare the time frame of the first domesticated cattle in Galicia to data from the connecting region of Cantabria to show a plausible connection between the Neolithization of these two regions. Our data shows a close relationship of the early domesticated cattle of Galicia and modern cow breeds and gives a general insight into cattle phylogeny. We conclude that settlers migrated to this region of Spain from Europe and introduced common European breeds to Galicia.