The fruit size of a cultivated olive tree is consistently larger than its corresponding wild relatives because fruit size is one of the main traits associated with olive tree domestication. Additionally, large fruit size is one of the main objectives of modern olive breeding programs. However, as the long juvenile period is one main hindrance in classic breeding approaches, obtaining genetic markers associated with this trait is a highly desirable tool. For this reason, GWAS analysis of both genetic markers and the genes associated with fruit size determination, measured as fruit weight, was herein carried out in 50 genotypes, of which 40 corresponded to cultivated and 10 to wild olive trees. As a result, 113 genetic markers were identified, which showed a very high statistically significant correlation with fruit weight variability, p < 10−10. These genetic markers corresponded to 39 clusters of genes in linkage disequilibrium. The analysis of a segregating progeny of the cross of “Frantoio” and “Picual” cultivars allowed us to confirm 10 of the 18 analyzed clusters. The annotation of the genes in each cluster and the expression pattern of the samples taken throughout fruit development by RNAseq enabled us to suggest that some studied genes are involved in olive fruit weight determination.