Natural killer (NK) cells are programmed to kill target cells without prior antigen priming. Because of their potent cytolytic activities, NK cells are one of the key cell types involved in dismantling allografts. However, in certain transplant models, NK cells also express potent immunoregulatory properties that promote tolerance induction. The precise mechanism for such striking dichotomy remains unknown. In the present study, we showed in a skin transplant model that the skin allografts contain a subset of antigen-presenting cells (APCs) that can home to the recipient mice. We also showed that such graft-derived APCs are usually destroyed by the host NK cells. But in the absence of NK cells, donor APCs can survive and then migrate to the host lymphoid and extralymphoid sites where they directly stimulate the activation of alloreactive T cells. T cells activated in the absence of NK cells are more resistant to costimulatory blockade treatment, and under such conditions stable skin allograft survival is difficult to achieve. Our study identified a novel role for NK cells in regulating T cell priming in transplant models, and may have important clinical implications in tolerance induction.