This paper presents a mechanical model and a shape optimization procedure for masonry vaults. The model is based on the basic assumption that such structures exhibit a no-tension membrane state of stress across a thrust surface S. Thus, the static problem of the vault is reduced to the search for a shape of S which ensures membrane equilibrium under suitable no-tension and position constraints (optimal shape). A discrete formulation of the model is obtained through a non-conforming variational method which makes use of polyhedral approximations to the thrust surface and the potential of the membrane stress (Pucher’s approach). It leads to a representation of such a stress field by a discrete network of compressive forces. The paper includes some numerical examples underlying the performance of the proposed solution search strategy.