Natural killer (NK) cells exhibit potent activity in pre-clinical models of diverse hematologic malignancies and solid tumors and infusion of high numbers of NK cells, either autologous or allogeneic, after their ex vivo expansion and activation, has been feasible and safe in clinical studies. To systematically define molecular features in human tumor cells which determine their degree of sensitivity to human allogeneic NK cells, we quantified the NK cell responsiveness of hundreds of molecularly-annotated “DNA-barcoded” solid tumor cell lines in multiplexed format (PRISM; Profiling Relative Inhibition Simultaneously in Mixtures approach), correlating cytotoxicity scores for each cell line with the CCLE transcriptional data (RNA-seq), to reveal genes that are associated with resistance or sensitivity to NK cells. In addition, we applied genome-scale CRISPR-based gene editing screens in several solid tumor cell lines to interrogate, at a functional level, which genes regulate tumor cell response to NK cells. Based on these orthogonal studies, NK sensitive tumor cells tend to exhibit high levels of the NK cell-activating ligand B7-H6 (NCR3LG1); low levels of the inhibitory ligand HLA-E; microsatellite instability (MSI) status; high transcriptional signature for chromatin remodeling complexes and low antigen presentation machinery genes. Treatment with an HDAC inhibitor reduced the sensitivity of SW620 colon cancer cells, increased antigen presentation machinery, including HLA-E, and reduced B7-H6. Importantly, we observe that transcriptional signatures of NK cell-sensitive tumor cells correlate with immune checkpoint inhibitor resistance in clinical samples. Strikingly, comprehensive analysis of the CCLE transcriptional signatures revealed that cell lines with mesenchymal-like program tend to be more sensitive to NK cells treatment, compared with cell lines of epithelial-like program. Indeed, mesenchymal tumors tend to have lower expression of antigen presentation machinery in both CCLE and TCGA, suggesting a link between these two machieneries. This study provides a comprehensive map of mechanisms regulating tumor cell responses to NK cells, with implications for future biomarker-driven applications of NK cell immunotherapies.