In the present study, effectiveness of social problem solving training to improve interpersonal relationships, social desirability, and executive functions were examined. This study was conducted using a quasi-experimental method with pretest-posttest without control group. A total of 85 subjects, preschool children and first and second- grade students, using available sampling procedure, participated in the study. The cognitive program ICPS was taught in each class for five months by the trained classroom teachers. The program was presented to the subjects twice a week. Measures used were the Early Childhood Behavior Rating Scale-Teacher Form, Wisconsin Card Sorting Test, and Social Desirability Inventory. The results using descriptive statistics and repeated measures to compare pre-test and post-test scores indicated that the intervention program was significantly effective in decreasing scores of Overt Physical Aggression, Relational /Emotional Aggression, and increasing scores of Social Desirability. In addition, the findings indicated that the intervention program was significantly effective in increasing Categories Achieved and decreasing Perseverative Errors. Results of the present study were consistent with other research and confirmed the effectiveness of interventions based on cognitive problem solving in social relationships. At the end, importance of problem solving skills training, as part of school’s curriculum were discussed.