Experimental evolution has been used for various biotechnological applications including protein and microbial cell engineering, but less commonly in the field of oncolytic virotherapy. Here, we sought to adapt a rapidly evolving RNA virus to cells deficient for the tumor suppressor gene p53, a hallmark of cancer cells. To achieve this goal, we established four independent evolution lines of the vesicular stomatitis virus (VSV) in p53-knockout mouse embryonic fibroblasts (p53−/− MEFs) under conditions favoring the action of natural selection. We found that some evolved viruses showed increased fitness and cytotoxicity in p53−/− cells but not in isogenic p53+/+ cells, indicating gene-specific adaptation. However, full-length sequencing revealed no obvious or previously described genetic changes associated with oncolytic activity. Half-maximal effective dose (EC50) assays in mouse p53-positive colon cancer (CT26) and p53-deficient breast cancer (4T1) cells indicated that the evolved viruses were more effective against 4T1 cells than the parental virus or a reference oncolytic VSV (MΔ51), but showed no increased efficacy against CT26 cells. In vivo assays using 4T1 syngeneic tumor models showed that one of the evolved lines significantly delayed tumor growth compared to mice treated with the parental virus or untreated controls, and was able to induce transient tumor suppression. Our results show that RNA viruses can be specifically adapted typical cancer features such as p53 inactivation, and illustrate the usefulness of experimental evolution for oncolytic virotherapy.