We present a highly effective algorithmic approach for generating differentially private synthetic data in a bounded metric space with near-optimal utility guarantees under the 1-Wasserstein distance. In particular, for a dataset in the hypercube $[0,1]^d$, our algorithm generates synthetic dataset such that the expected 1-Wasserstein distance between the empirical measure of true and synthetic dataset is $O(n^{-1/d})$ for $d>1$. Our accuracy guarantee is optimal up to a constant factor for $d>1$, and up to a logarithmic factor for $d=1$. We further study the variations of this algorithm in low-dimensional settings and streaming inputs to overcome the curse of high-dimensionality.