Mobile devices are increasingly becoming vulnerable to a variety of network-level security threats including different types of man-in-the-middle (MITM) attacks such as message interceptions and modifications, eavesdropping on calls and text messages, message spoofing and phishing attacks. In this paper, we propose the design and implementation of Secure Mobile Identities (SMI), a secure key-exchange protocol that enables a mobile user to establish a secure and trustworthy communication channel with other mobile users in the face of external adversaries. The design of SMI places initial bootstrap trust on the cellular providers and builds upon the basic assumption that cellular networks offer a unique "partially trustworthy one-way" channel to connected mobile devices; unlike Internet routes which can be hijacked, the cellular network routing layer is closed thereby forcing the MITM attacker to attack only the last-hop wireless channel between the tower and the device. Building on this assumption, SMI provides a spatio-temporal, multi-path, repetitive challenge-response key exchange protocol to enable two mobile entities to tag every key exchange with a (location, time, path) triplet and leverage diversity across paths to build a trust reputation for every key. The security of SMI can be further enhanced with the use of external trusted entities providing non-forgeable trusted location signatures (e.g. trusted GPS, trusted cell towers, physical synchronization points). In this paper, we demonstrate the effectiveness of our protocol using a prototype implementation and demonstrate ease of use across a variety of real-world channels. We also show how the SMI abstraction can enable new forms of secure mobile applications including secure cash transfer, secure physical identities and secure file exchange.