Rate and diversity impose a fundamental trade-off in wireless communication. High-rate space-time codes come at a cost of lower reliability (diversity), and high reliability (diversity) implies a lower rate. However, wireless networks need to support applications with very different Quality-of-Service (QoS) requirements, and it is natural to ask what characteristics should be built into the physical layer link in order to accomodate them. In this paper we de- sign high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations while the embedded high-diversity code provides guarantees that at least part of the information is received reliably. We provide constructions of linear and non-linear codes for a fixed transmit alphabet constraint. The non-linear constructions are a natural generalization to wireless channels of multilevel codes developed for the AWGN chan- nel that are matched to binary partitions of QAM and PSK constellations. The importance of set-partitioning to code design for the wireless channel is that it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain. We investigate the systems implications of embedded diversity codes by examining value to unequal error protection, rate opportunism and packet delay optimiza- tion. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate SNR regimes.