Autism spectrum disorders (ASD) are characterized by social communication deficits, cognitive rigidity, and repetitive stereotyped behaviors. Mesenchymal stem cells (MSC) have a paracrine regenerative effect, and were speculated to be a potential therapy for ASD. The BTBR inbred mouse strain is a commonly used model of ASD as it demonstrates robust behavioral deficits consistent with the diagnostic criteria for ASD. BTBR mice also exhibit decreased BDNF signaling and reduced hippocampal neurogenesis. In our studies we found that transplantation of MSC resulted in a reduction of stereotypical behaviors, a decrease in cognitive rigidity and an improvement in social behavior. Tissue analysis revealed elevated BDNF protein levels in the hippocampus accompanied by increased hippocampal neurogenesis. Moreover, the behavioral benefits were seen long after the transplantation (6 months), suggesting for nonreversible changes that benefit especially the social behaviors. Our study suggests a novel therapeutic approach which may be translatable to ASD patients in the future.