The vertebrate innate immune system consists of inflammatory cells and soluble mediators that comprise the first line of defense against microbial infection and, importantly, trigger antigen-specific T and B cell responses that lead to lasting immunity. The molecular mechanisms responsible for microbial non-self recognition by the innate immune system have been elucidated for a large number of pathogens. How the innate immune system recognizes non-microbial non-self, such as organ transplants, is less clear. In this review, we approach this question by describing the principal mechanisms of non-self, or 'damaged' self, recognition by the innate immune system (pattern recognition receptors, the missing self theory, and the danger hypothesis) and discussing whether and how these mechanisms apply to allograft rejection.