This paper presents a new routing discovery strategy for heterogeneous MANETs. Node heterogeneity is modeled in terms of: types and number of different interfaces, power, and transmission ranges. Our proposed route discovery algorithm is implemented on the top of On-demand Tree-based Routing Protocol (OTRP) and hence it is called OTRP Heterogeneity-Aware (OTRP-HA). OTRP-HA utilizes node heterogeneity and optimizes route discovery to reduce overheads and ensures connectivities between different types of nodes with different interfaces. Each node makes its own decision to participate in the route discovery process according to its location, local density, and available resources. Simulation results show that OTRP-HA outperforms OTRP and AODV and it reduces overheads as a number of nodes and traffic increase, while it also further prolongs the lifetime of battery-powered single-interface nodes when compared to AODV.