We propose the coordinated use of multiple heterogeneous wireless technologies to optimize the latency and power consumption of mobile systems during device discovery and connection setup. We present several multi-radio connection establishment techniques, which exploit the wide disparity in the power and performance characteristics of different radios to create an efficient and flexible communication subsystem. Our techniques enable mobile devices to combine the strengths of these diverse technologies, thereby powering down higher power radios when their capabilities are not needed and using a hierarchical radio structure for device discovery and connection setup. Experiments using a prototype multi-radio device show that the use of radio hierarchies results in significant power savings, and often improves connection setup latency as well.