Although major histocompatibility complex (MHC) class II-restricted CD4 T cells are well appreciated for their contribution to peripheral tolerance to tissue allografts, little is known regarding MHC class I-dependent reactivity in this process. Here we show a crucial role for host MHC class I-dependent NK cell reactivity for allograft tolerance in mice induced through either costimulation blockade using CD154-specific antibody therapy or by targeting LFA-1 (also known as CD11a). Tolerance induction absolutely required host expression of MHC class I, but was independent of CD8 T cell-dependent immunity. Rather, tolerance required innate immunity involving NK1.1(+) cells, but was independent of CD1d-restricted NKT cells. Therefore, NK cells seem to be generally required for induction of tolerance to islet allografts. Additional studies indicate that CD154-specific antibody-induced allograft tolerance is perforin dependent. Notably, NK cells that are perforin competent are sufficient to restore allograft tolerance in perforin-deficient recipients. Together, these results show an obligatory role for NK cells, through perforin, for induction of tolerance to islet allografts.