We define Orlicz-Sobolev spaces on an arbitrary metric space with
a Borel regular outer measure, and we develop a capacity theory
based on these spaces. We study basic properties of capacity and
several convergence results. We prove that each Orlicz-Sobolev
function has a quasi-continuous representative. We give estimates
for the capacity of balls when the measure is doubling. Under
additional regularity assumption on the measure, we establish
some relations between capacity and Hausdorff measures.