The innate immune system existed prior to the emergence of adaptive immunity in sharks and higher vertebrates. Homologues of many mammalian innate immune-system elements such as the toll-like receptors exist in species as distant as Drosophila. Selective pressure has led to the development of highly conserved, soluble, and cell-surface receptors that recognize functionally essential molecules shared by microbial pathogens. It is thought that molecular patterns that exquisitely distinguish pathogenic cells from mammalian cells are recognized. Therefore, it would seem unlikely that innate immune-system elements should recognize mammalian tissues. However, there is increasing evidence to suggest that this is the case and that innate immunity promotes rejection of transplanted mammalian tissues, particularly those from other species (xenografts). Evidence for innate recognition of mammalian grafts, the nature of this recognition, and the bi-directional interactions between innate and adaptive immunity that contribute to graft rejection are discussed in this review, with the emphasis on nonvascular xenografts.