Existing paradigms of dynamic spectrum access (DSA) impose a 'foe' relationship between the primary users (PUs) and the secondary users (SUs), where SUs may access the spectrum only when PUs cease using it, and the resurgence of PU traffic disrupts SU traffic. To comply with such stringent DSA policies, SUs behave conservatively to sense and access the spectrum, which may result in an actual spectrum utilization lower than what is feasible. Applying network coding (NC), this paper proposes a new DSA architecture termed network coding relayed DSA (NCR-DSA). In NCR-DSA, NC is conducted between PU traffic and SU traffic to enable SU nodes to serve as relays for PU traffic between PU nodes. While relaying PU traffic, SU nodes seek opportunities to encode SU traffic onto PU traffic for transmission, i.e., SU packets are 'piggybacked' via NC on PU packets without incurring separate spectrum access. A Linear Programming model has been developed to analyze the throughput gain of NCR-DSA in comparison with existing DSA paradigms. Numerical results show that NCR-DSA significantly increases throughput for both PU and SU, creating a 'win-win' DSA paradigm.