Among mammals, placental invasion is correlated with vulnerability to malignancy. Animals with more invasive placentation (for example, humans) are more vulnerable to malignancy. To explain this correlation, we propose the hypothesis of Evolved Levels of Invasibility proposing that the evolution of invasibility of stromal tissue affects both placental and cancer invasion. We provide evidence for this using an in vitro model. We find that bovine endometrial and skin fibroblasts are more resistant to invasion than are their human counterparts. Gene expression profiling identified genes with high expression in human but not in bovine fibroblasts. Knocking down a subset of them in human fibroblasts leads to stronger resistance to cancer cell invasion. Identifying the evolutionary determinants of stromal invasibility can provide important insights to develop rational antimetastatic therapeutics.