Mobile ad-hoc Networks (MANETs) are self-managing wireless networks without relying on any central administration. Each MANET node can connect itself to its neighbors on an ad-hoc basis and communicate with other nodes through its neighbors over multi-hop wireless links. The routes to destination nodes are discovered in an on-demand fashion by broadcasting customized messages called RREQ (Route REQuest). The RREQ messages are re-broadcasted by each of the subsequent receiving nodes until the RREQ arrives at the ultimate destination node which then responds back with the RREP (Route REPly) message to the original sending node to setup up the route. Continuously moving nodes and wireless nature of the communication links impose challenges to efficient broadcasting of RREQs and impact routing performance. A node receiving a RREQ message should be cautious on re-broadcasting it to avoid the Broadcast Storm Problem (BSP) on one side, and on another side, maximizing the reachability of the RREQ message to the destination node. This paper presents a novel distributed algorithm CAPB (Channel Adaptive Probabilistic Broadcasting) to decide the re-broadcasting of RREQ messages for individual MANET nodes in a probabilistic manner. The algorithm takes into account the neighboring node density as well as SINR (Signal to Interference plus Noise Ratio) to decide rebroadcast-probability dynamically. The proposed algorithm has been implemented in the standard AODV routing protocol using the ns-2 simulator. The simulation results have shown that the proposed algorithm outperforms the standard AODV and three state-of-the-art competitor schemes in terms of routing overhead, throughput, end-to-end delay and energy consumption significantly. The proposed algorithm improves network performance and battery life at the same time.