Monocyte/macrophage and natural killer (NK) cells are partners from a phylogenetic standpoint of innate immune system development and its evolutionary progressive interaction with adaptive immunity. The equally conservative ways of development and differentiation of both invertebrate hemocytes and vertebrate macrophages are reviewed. Evolutionary conserved molecules occurring in macrophage receptors and effectors have been inherited by vertebrates after their common ancestor with invertebrates. Cytolytic functions of mammalian NK cells, which are rooted in immune cells of invertebrates, although certain NK cell receptors (NKRs) are mammalian new events, are characterized. Broad heterogeneity of macrophage and NK cell phenotypes that depends on surrounding microenvironment conditions and expression profiles of specific receptors and activation mechanisms of both cell types are discussed. The particular tissue specificity of macrophages and NK cells, as well as their plasticity and mechanisms of their polarization to different functional subtypes have been underlined. The chapter summarized studies revealing the specific molecular mechanisms and regulation of NK cells and macrophages that enable their highly specific cross-cooperation. Attention is given to the evolving role of human monocyte/macrophage and NK cell interaction in pathogenesis of hypersensitivity reaction-based disorders, including autoimmunity, as well as in cancer surveillance and progression.