Magnetic frustrations and dimensionality play an important role in determining the nature of the magnetic long-range order and how it melts at temperatures above the ordering transition T_{N}. In this Letter, we use large-scale Monte Carlo simulations to study these phenomena in a class of frustrated Ising spin models in two spatial dimensions. We find that the melting of the magnetic long-range order into an isotropic gaslike paramagnet proceeds via an intermediate stage where the classical spins remain anisotropically correlated. This correlated paramagnet exists in a temperature range T_{N}<T<T^{*}, whose width increases as magnetic frustrations grow. This intermediate phase is typically characterized by short-range correlations; however, the two-dimensional nature of the model allows for an additional exotic feature-formation of an incommensurate liquidlike phase with algebraically decaying spin correlations. The two-stage melting of magnetic order is generic and pertinent to many frustrated quasi-2D magnets with large (essentially classical) spins.