We describe QoSMap, an overlay construction mechanism which computes high quality overlay networks for applications having stringent constraints on hop-degrading QoS metrics and provides resilience against the Internet’s unpredictable network behavior. QoSMap implements three features to achieve the QoS and resiliency goals. In order to provide high QoS, it constructs overlay communication edges with short but efficient underlay paths. In case of QoS violations due to changing network conditions, QoSMap utilizes supplemental backup paths, which are specifically constructed in order to extend overlay lifetimes. QoSMap also avoids nodes that have experienced recent QoS failure, further improving the resilience of the overlays. PlanetLab experiments prove the ability of QoSMap to construct efficient and resilient overlays for applications with stringent QoS constraints of latency and packet loss for a variety of topologies. QoSMap-constructed overlays significantly outperform overlays constructed without the three QoSMap features. The results also reveal the usability and effectiveness of QoSMap to construct near-optimal solution in a short amount of time, compared to the optimal solution which has a very high time complexity.