Vehicular Ad Hoc Network (VANET) is a growing field of Intelligent Transportation System (ITS). It holds a significant use in managing the emergencies and providing infotainment in a moving vehicle. In VANET due to the high mobility of vehicle and rapid topology change, finding a short and stable route is a complex problem. In this paper, we proposed a routing protocol to find a short and stable route: Bacterial Foraging Optimization for Zone Based Routing (BFOZBR) protocol for VANET. This BFOZBR protocol uses two techniques to handle the routing problem. The first technique used is Zone Based Routing (ZBR) that divides the network into zones, and nodes distributed into zones on the basis of similar characteristics like velocity, direction, and position, that increases the stability. The second technique used is bacterial foraging optimization (BFO) to find the best route in a short period. We carried simulation for two cases. In the first case, we considered the different transmission rate at fix velocity. In the second case, we considered different node velocity at fix transmission rate. The simulation results of BFOZBR analyzed and compared with other routing protocol Fuzzy Zone Based Routing (FZBR) protocol. We evaluated routing performance by four performance parameters: average delay, packet drop ratio, packet delivery ratio, and overhead. We selected theses parameters because they provide Quality of Service (QoS). Simulation results revealed that the packet delivery ratio is high, and the packet drop ratio is low in BFOZBR compared to FZBR, which indicates that the discovered route is stable. The results also revealed that end-to-end delay is also less in BFOZBR compared to FZBR, which indicates that the discovered route is a short route.