Standard approaches to cognitive remediation can suffer from limited skill transferability to patients’ life. Complex virtual environments (VEs) enable us to create ecologically valid remediation scenarios while preserving laboratory conditions. Nevertheless, the feasibility and efficacy of these programs in psychiatric patients are still unknown. Our aim was to compare the feasibility and efficacy of a novel rehabilitation program, designed in complex VEs, with standard paper–pencil treatment in patients with schizophrenia and major depressive disorder. We recruited 35 participants to complete a VE rehabilitation program and standard treatment in a crossover pilot study. Twenty-eight participants completed at least one program, 22 were diagnosed with schizophrenia and 6 with major depressive disorder. Participant’s performance in the representative VE training task significantly improved in terms of maximum achieved difficulty (p ≤ 0.001), speed (p < 0.001) and efficacy (p ≤ 0.001) but not in item performance measure. Neither the standard treatment nor the VE program led to improvement in standardized cognitive measures. Participants perceived both programs as enjoyable and beneficial. The refusal rate was higher in the VE program (8.6%) than in the standard treatment (0%). But in general, the VE program was well-accepted by the psychiatric patients and it required minimal involvement of the clinician due to automatic difficulty level adjustment and performance recording. However, the VE program did not prove to be effective in improving cognitive performance in the standardized measures.