The deluge of date rate in today's networks imposes a cost burden on the backhaul network design. Developing cost-efficient backhaul solutions becomes an exciting, yet challenging, problem. Traditional technologies for backhaul networks, including either radio-frequency (RF) backhauls or optical fibers (OF). While RF is a cost-effective solution as compared with OF, it supports the lower data rate requirements. Another promising backhaul solution is the free-space optics (FSO) as it offers both a high data rate and a relatively low cost. The FSO, however, is sensitive to nature conditions, e.g., rain, fog, and line-of-sight. This paper combines both the RF and FSO advantages and proposes a hybrid RF/FSO backhaul solution. It considers the problem of minimizing the cost of the backhaul network by choosing either OF or hybrid RF/FSO backhaul links between the base stations, so as to satisfy data rate, connectivity, and reliability constraints. It shows that under a specified realistic assumption about the cost of OF and hybrid RF/FSO links, the problem is equivalent to a maximum weight clique problem, which can be solved with moderate complexity. Simulation results show that the proposed solution shows a close-to-optimal performance, especially for reasonable prices of the hybrid RF/FSO links. They further reveal that the hybrid RF/FSO is a cost-efficient solution and a good candidate for upgrading the existing backhaul networks. © 2016 IEEE.