Aegean Graben System is a significant member of the complex geology of western Turkey. The depths to the metamorphic basement reliefs in two major grabens have been reported by many geophysical studies. However, the sediment thicknesses of these graben basins still remain controversial due to the findings differing from each other. Thus, we have inverted the gravity data of the sedimentary cover-metamorphic basement using a stochastic derivative-free vector-based metaheuristic named differential evolution algorithm (DEA). This is the first application of DEA adapted to the basement relief depth problem. Model parametrizations have been achieved by discretizing the basins using a group of juxtaposed vertical blocks. Before the inversion studies, mathematical nature of the inverse problem has been investigated via prediction cost function/error energy maps for some block pairs using a hypothetical basin model. These maps have shown the resolvability characteristic of the block thicknesses on such inversion problem. Parameter tuning studies for the optimum mutation constant/weighting factor have been performed to increase the efficiency of the algorithm. The synthetic data have been successfully inverted via the tuned control parameter and some smoothing operators. Probability density function (PDF) analyses have shown that the best solutions are within the confidence interval limits without uncertainties. In the field data case, long-wavelength anomalies caused by both crustal and deeper effects have been removed from the complete Bouguer anomalies through 2-D finite element method using the element shape functions. Some profiles extracted from the residual gravity anomaly map have been used for the inversion and obtained results have shown that the maximum depths to the metamorphic basement reliefs in the grabens are shallower than the findings of the previous studies. Information obtained from the lithological logs drilled in the grabens has supported our results. Moreover, PDF analyses have indicated the reliability of the obtained solutions without uncertainties.