Moiré superlattice systems such as transition metal dichalcogenide heterobilayers have garnered significant recent interest due to their promising utility as tunable solid state simulators. Recent experiments on a WSe2/WS2 heterobilayer detected incompressible charge ordered states that one can view as generalized Wigner crystals. The tunability of the transition metal dichalcogenide heterobilayer Moiré system presents an opportunity to study the rich set of possible phases upon melting these charge-ordered states. Here we use Monte Carlo simulations to study these intermediate phases in between incompressible charge-ordered states in the strong coupling limit. We find two distinct stripe solid states to be each preceded by distinct types of nematic states. In particular, we discover microscopic mechanisms that stabilize each of the nematic states, whose order parameter transforms as the two-dimensional E representation of the Moiré lattice point group. Our results provide a testable experimental prediction of where both types of nematic occur, and elucidate the microscopic mechanism driving their formation. © 2022, The Author(s).