Vehicular ad hoc networks (VANETs) are a special form of networks which enable the communications among vehicles on roads with no need of fixed infrastructure. The special characteristics of VANETs like high mobility and frequent changes of network topology create challenging technical issues, which need to be resolved in order to deploy these networks effectively. Routing reliability is one of the most critical issues where, the established route should be the most reliable one among all other routes to the destination. In this paper, we propose a new reliability-based routing scheme for VANETs in order to facilitate Quality of Service (QoS) support in the routing process. The link reliability is defined as the probability that an active link remains available for a certain time interval. The location and velocity information of vehicles are used to calculate link reliability accurately. We demonstrate that the proposed scheme improves significantly the performance of the standard Ad hoc On-demand Distance Vector (AODV) routing protocol.