The Conditional Gradient method offers a computationally efficient, projection-free framework for constrained problems; however, in nonconvex settings it may converge to stationary points of low quality. We propose the Voronoi Conditional Gradient (VCG) method, a geometric heuristic that systematically explores the feasible region by constructing adaptive Voronoi partitions from previously discovered stationary points. VCG incrementally refines a Voronoi decomposition of the feasible region and initiates new conditional gradient runs from interior points of underexplored cells, thereby promoting systematic coverage of the search space. We evaluate VCG on two classes of NP-hard problems and demonstrate that it consistently finds high-quality candidate solutions.