We have developed a new level-set-based structural parameterization for joint inversion of gravity and traveltime data, so that density contrast and seismic slowness are simultaneously recovered in the inverse problem. Because density contrast and slowness are different model parameters of the same survey domain, we assume that they are similar in structure in terms of how each property changes and where the interface is located, so that we are able to use a level-set function to parameterize the common interface shared by these two model parameters. The level-set parameterization makes it easy to maintain the structural similarity between the two geophysical properties. The inversion of gravity and traveltime data is carried out by minimizing a joint data-fitting function with respect to density contrast, slowness, as well as the level-set function. An adjoint state method is used to compute the traveltime gradient efficiently. We have tested our algorithm on various synthetic examples, including a 2D ovoid model and the 2D SEG/EAGE salt model. The results show that the joint-inversion algorithm effectively improves recovery of subsurface features. To the best of our knowledge, this is the first time that the level-set method was used to structurally link density contrast and slowness distribution systematically.