Computationally hard problems, including combinatorial optimization, can be mapped into the problem of finding the ground-state of an Ising Hamiltonian. Building physical systems with collective computational ability and distributed parallel processing capability can accelerate the ground-state search. Here, we present a continuous-time dynamical system (CTDS) approach where the ground-state solution appears as stable points or attractor states of the CTDS. We harness the emergent dynamics of a network of phase-transition nano-oscillators (PTNO) to build an Ising Hamiltonian solver. The hardware fabric comprises of electrically coupled injection-locked stochastic PTNOs with bi-stable phases emulating artificial Ising spins. We demonstrate the ability of the stochastic PTNO-CTDS to progressively find more optimal solution by increasing the strength of the injection-locking signal – akin to performing classical annealing. We demonstrate in silico that the PTNO-CTDS prototype solves a benchmark non-deterministic polynomial time (NP)-hard Max-Cut problem with high probability of success. Using experimentally calibrated numerical simulations, we investigate the performance of the hardware with increasing problem size. We show the best-in-class energy-efficiency of 3.26x107 solutions/sec/Watt which translates to over five orders of magnitude improvement when compared with digital CMOS, superconducting qubit and photonic Ising solver approaches. We also demonstrate an order of magnitude improvement over a discrete-time memristor-based Hopfield network approach. Such an energy efficient CTDS hardware exhibiting high solution-throughput/Watt can find application in industrial planning and manufacturing, defense and cyber-security, bioinformatics and drug discovery.