This study proposes a systematic approach for planning and operating a one-way vehicle-sharing system (VSS) under demand uncertainty. It investigates the distribution of parking spaces and vehicles considering stochastic demand and interactions with the major operational decisions, namely vehicle redistribution activities. An optimization model is formulated that aims to determine the best deployment strategy for minimizing overall cost while achieving a certain level of service (LoS). Then, a simulation-based solution approach based on a discrete-event simulator (DES), Particle Swarm Optimization (PSO), and Optimal Computing Budget Allocation (OCBA) is devised to solve the mathematical model. The methodology is then applied to a car-sharing system in Singapore. Results demonstrate that considering rebalancing activities is imperative in making deployment strategies. The case study also provides managerial insights regarding designing and operating one-way VSS.