Car sharing holds a promise of reducing trafficcongestion and pollution in cities as well as of boosting the useof public transport when used as a last-mile solution in a multimodaltransportation scenario. Despite this huge potential,several problems related to the deployment and operations ofcar sharing systems have yet to be fully addressed. In thiswork, we focus on station-based car sharing and we define anoptimization problem for the deployment of its stations. Thegoal of this problem is to find the minimum cost deployment(in terms of number of stations and their capacity) that canguarantee a pre-defined level of service to the customers (interms of probability of finding an available car/parking space).This problem combines insights from queueing theory (usedto model the stochastic demand for cars/parking spaces at thestations) with a variant of the classical set covering problem.For its evaluation, we use a trace of more than 100,000 pickupand drop-off events at a free-floating car sharing service in TheNetherlands, which are used to model the input demand of thecar sharing system. Our results show that the proposed solutionis able to strike the right balance between cost minimisationand quality of service, outperforming three alternative schemesused as benchmarks.