Metaheuristic algorithms such as simulated annealing (SA) has been implemented for optimization in combinatorial problems, especially for discreet problems. SA employs a stochastic search, where high-energy transitions (“hill-climbing”) are allowed with a temperature-dependent probability to escape local optima. Ising spin glass systems have properties such as spin disorder and “frustration” and provide a discreet combinatorial problem with high number of metastable states and ground-state degeneracy. In this work, we exploit subthreshold Boltzmann transport in complementary two-dimensional (2D) field effect transistors (p-type WSe2 and n-type MoS2) integrated with analog, non-volatile, and programmable floating-gate memory stack to develop in-memory computing primitives necessary for energy and area efficient hardware acceleration of SA for the Ising spin systems. We experimentally demonstrate > 800X search acceleration for 4×4 ferromagnetic, antiferromagnetic, and a spin glass system using SA compared to an exhaustive search using brute force trial at miniscule total energy expenditure of ~120 nJ. Our hardware realistic numerical simulations further highlight the astounding benefits of SA in accelerating the search for larger spin lattices.