In this paper, we investigate the connectivity of vehicular ad hoc networks in free-flow traffic situation with channel randomness. In order to illustrate the realistic environment, we consider that vehicles are distributed in free-flow highway according to a Poisson point process, and signal propagation between connected vehicles is subjected to log-normal shadowing effects. We obtain the distribution of the space headway between successive vehicles and the distribution of signal coverage, which allows us to use the equivalent M/G/∞ queue theory to model the connectivity of VANETs in the form of average broadcast percolation distance and average number of connected nodes. Then, extensive simulation studies are conducted to evaluate the obtained results. The analytical model presented here is able to describe the impact of various system parameters, including traffic parameters and signal propagation parameters on the connectivity. We use our analytical results, along with the common signal propagation data, to understand impact of channel randomness on the connectivity of VANETs.