Overlay network virtualization quickly gains traction in today's multi-tenant data centers due to its ability to provide independent virtual networks, at scale, along with complete isolation from the underlying physical network. Despite the benefits, performance degradation due to the imposed perpacket encapsulation overhead is a serious impediment. Mitigation approaches are mostly hardware based and thus depend on costly networking gear upgrades and suffer from lesser flexibility and longer times to market, compared to software solutions. Software optimizations proposed so far are limited in scope, applicability, and interoperability. In this paper we present NoEncap, a software-only optimization, capable of eliminating almost completely the overheads, while fully preserving the benefits of an overlay-based network virtualization.