Treatment of advanced metastatic colorectal cancer (mCRC) patients is associated with a poor prognosis and significant morbidity. Moreover, targeted therapies such as anti-epidermal growth factor receptor (EGFR) have no effect in metastatic patients with tumors harboring a mutation in the RAS gene. The failure of conventional treatment to improve outcomes in mCRC patients has prompted the development of adoptive immunotherapy approaches including natural killer (NK)-based therapies. In this study, after confirmation that patients’ NK cells were not impaired in their cytotoxic activity, evaluated against long-term tumor cell lines, we evaluated their interactions with autologous mCRC cells. Molecular and phenotypical evaluation of mCRC cells, expanded in vitro from liver metastasis, showed that they expressed high levels of polio virus receptor and Nectin-2, whereas UL16-binding proteins were less expressed in all tumor samples evaluated. Two different patterns of MICA/B and HLA class I expression on the membrane of mCRC were documented; approximately half of mCRC patients expressed high levels of these molecules on the membrane surface, whereas, in the remaining, very low levels were documented. Resting NK cells were unable to display sizeable levels of cytotoxic activity against mCRC cells, whereas their cytotoxic activity was enhanced after overnight or 5-day incubation with IL-2 or IL-15. The susceptibility of NK-mediated mCRC lysis was further significantly enhanced after coating with cetuximab, irrespective of their RAS mutation and HLA class I expression. These data open perspectives for combined NK-based immunotherapy with anti-epidermal growth factor receptor antibodies in a cohort of mCRC patients with a poor prognosis refractory to conventional therapies.