A good starting model is imperative in full-waveform inversion (FWI) because it solves a least-squares inversion problem using a local gradient-based optimization method. A suboptimal starting model can result in cycle skipping leading to poor convergence and incorrect estimation of subsurface properties. This problem is especially crucial for salt models because the strong velocity contrasts create substantial time shifts in the modeled seismogram. Incorrect estimation of salt bodies leads to velocity inaccuracies in the sediments because the least-squares gradient aims to reduce traveltime differences without considering the sharp velocity jump between sediments and salt. We have developed a technique to estimate velocity models containing salt bodies using a combination of global and local optimization techniques. To stabilize the global optimization algorithm and keep it computationally tractable, we reduce the number of model parameters by using sparse parameterization formulations. The sparse formulation represents sediments using a set of interfaces and velocities across them, whereas a set of ellipses represents the salt body. We use very fast simulated annealing (VFSA) to minimize the misfit between the observed and synthetic data and estimate an optimal model in the sparsely parameterized space. The VFSA inverted model is then used as a starting model in FWI in which the sediments and salt body are updated in the least-squares sense. We partition model updates into sediment and salt updates in which the sediments are updated like conventional FWI, whereas the shape of the salt is updated by taking the zero crossing of an evolving level set surface. Our algorithm is tested on two 2D synthetic salt models, namely, the Sigsbee 2A model and a modified SEG Advanced Modeling Program (SEAM) Phase I model while fixing the top of the salt. We determine the efficiency of the VFSA inversion and imaging improvements from the level set FWI approach and evaluate a few sources of uncertainty in the estimation of salt shapes.