In vehicular ad hoc networks (VANETs), message dissemination to one or more vehicles is very challenging, due to frequent network disconnections and uncertain locations of the destination vehicles. Deploying roadside units (RSUs) is a possible solution to overcome the challenges, but it often requires a large amount of investment. In this paper, we propose the idea of Parking Backbone, which does not need any RSUs but leverages a virtual overlay network formed by outside parked vehicles to track vehicles and to disseminate messages between moving vehicles. Our scheme consists of three parts. At first, to each road, parked vehicles both at roadside and off street are grouped into a cluster as far as possible. An urban overlay network is established based on this type of clusters for data transmission. Secondly, to a specific vehicle, a daily mobility model is established, to determine its location through a corresponding location prediction algorithm. Finally, a novel message delivery scheme is designed to efficiently transmit messages to destination vehicles through the proposed virtual overlay network. Thanks to the extensive and stable outside parking in cities, once grouped into the overlay structure, data transmission can be easily achieved over the Parking Backbone. Extensive simulation results prove that our scheme achieves high performance in message dissemination.