Topology optimization can be used to design structures that operate in adverse environments and are subject to constraints on their natural frequencies. In this work, we explore the use of Galerkin Difference (GD) methods to analyze and optimize the natural frequency response of topology optimized structures. GD methods utilize high-order basis functions without element-interior degrees of freedom, resulting in discretizations that resemble finite-difference stencils and possess excellent dispersion properties. GD methods are naturally defined on Cartesian meshes. To accommodate complex domain boundaries, we utilize a cut-cell approach in which the structural boundary is implicitly defined by a level-set function. At the boundary, the GD basis functions are modified to utilize degrees of freedom from the domain interior while preserving continuity. To enable topology optimization, the void region is modeled using a soft ersatz material, while interface conditions between the solid and void regions are imposed weakly with Nitsche’s method. The level-set function is smoothed via a filtering technique, and the optimization is performed using the method of moving asymptotes. Numerical results demonstrate the accuracy and efficiency of the proposed approach.