Immunological memory specific to previously encountered antigens is a cardinal feature of adaptive lymphoid cells. However, it is unknown whether innate myeloid cells retain memory of prior antigenic stimulation and respond to it more vigorously on subsequent encounters. In this work, we show that murine monocytes and macrophages acquire memory specific to major histocompatibility complex I (MHC-I) antigens, and we identify A-type paired immunoglobulin-like receptors (PIR-As) as the MHC-I receptors necessary for the memory response. We demonstrate that deleting PIR-A in the recipient or blocking PIR-A binding to donor MHC-I molecules blocks memory and attenuates kidney and heart allograft rejection. Thus, innate myeloid cells acquire alloantigen-specific memory that can be targeted to improve transplant outcomes.