The development of Vehicular Ad Hoc Networks (VANET) has brought many advantages to facilitate the deployment of the Intelligent Transportation System (ITS). However, without proper protection, VANETs can be vulnerable to severe cyber-attacks. This paper explores the threats to the VANETs and proposes a security scheme for VANETs with a Blockchain (VNB). Furthermore, the proposed VNB with Ethereum was developed. With a graphical user interface, experiments were conducted. For ad hoc communications, a vehicle can randomly select another vehicle, and VNB will authenticate the selected vehicle with the Blockchain and Trusted Authority (TA). Preliminary test results successfully proved that Blockchain can be the key technology to mitigate the security threats to VANETs.