An important tactical decision for vehicle rental providers is the design of a repositioning strategy to balance vehicle utilization with customer wait times due to vehicle unavailabilities. To address this problem, this article analyzes alternative repositioning strategies: a no-repositioning strategy, a customer repositioning strategy, and a vehicle repositioning strategy, using queuing network models that are able to handle stochastic demand and vehicle unavailabilities. Optimization models are formulated to determine the repositioning fractions for alternate strategies that minimize the rental provider’s cost by balancing repositioning costs with customer waiting penalty costs. The nonlinear optimization problems are challenging to solve because the objective functions are non-differentiable and the decision variables (such as effective arrival rates and customer repositioning fractions) are interrelated. Therefore, a two-phase sequential solution approach to estimate the repositioning fractions is developed. Phase 1 determines the effective arrival rates by developing an approximate network model, deriving structural results, determining a high-quality solution point, and refining the solution. Phase 2 determines the repositioning fractions by solving a transportation problem. Numerical experiments are used to evaluate the efficacy of the proposed solution approach, to analyze alternate repositioning strategies, and to illustrate how the developed techniques can be adopted to create a better readiness at a depot.