We present a new cosmological probe for galaxy clusters, the halo sparsity. This characterises halos in terms of the ratio of halo masses measured at two different radii and carries cosmological information encoded in the halo mass profile. Building upon the work of Balmes et al. (2014) we test the properties of the sparsity using halo catalogs from a numerical N-body simulation of ($2.6$ Gpc/h)$^3$ volume with $4096^3$ particles. We show that at a given redshift the average sparsity can be predicted from prior knowledge of the halo mass function. This provides a quantitative framework to infer cosmological parameter constraints using measurements of the sparsity of galaxy clusters. We show this point by performing a likelihood analysis of synthetic datasets with no systematics, from which we recover the input fiducial cosmology. We also perform a preliminary analysis of potential systematic errors and provide an estimate of the impact of baryonic effects on sparsity measurements. We evaluate the sparsity for a sample of 104 clusters with hydrostatic masses from X-ray observations and derive constraints on the cosmic matter density $Omega_m$ and the normalisation amplitude of density fluctuations at the $8$ Mpc h$^{-1}$ scale, $sigma_8$. Assuming no systematics, we find $Omega_m=0.42pm 0.17$ and $sigma_8=0.80pm 0.31$ at $1sigma$, corresponding to $S_8equiv sigma_8sqrt{Omega_m}=0.48pm 0.11$. Future cluster surveys may provide opportunities for precise measurements of the sparsity. A sample of a few hundreds clusters with mass estimate errors at a few percent level can provide competitive cosmological parameter constraints complementary to those inferred from other cosmic probes.