Background Trauma is prevalent amongst early psychosis patients and associated with adverse outcomes. Past trials of trauma-focused therapy have focused on chronic patients with psychosis/schizophrenia and comorbid Post-Traumatic Stress Disorder (PTSD). We aimed to determine the feasibility of a large-scale randomized controlled trial (RCT) of an Eye Movement Desensitization and Reprocessing for psychosis (EMDRp) intervention for early psychosis service users. Methods A single-blind RCT comparing 16 sessions of EMDRp + TAU v. TAU only was conducted. Participants completed baseline, 6-month and 12-month post-randomization assessments. EMDRp and trial assessments were delivered both in-person and remotely due to COVID-19 restrictions. Feasibility outcomes were recruitment and retention, therapy attendance/engagement, adherence to EMDRp treatment protocol, and the 'promise of efficacy' of EMDRp on relevant clinical outcomes. Results Sixty participants (100% of the recruitment target) received TAU or EMDR + TAU. 83% completed at least one follow-up assessment, with 74% at 6-month and 70% at 12-month. 74% of EMDRp + TAU participants received at least eight therapy sessions and 97% rated therapy sessions demonstrated good treatment fidelity. At 6-month, there were signals of promise of efficacy of EMDRp + TAU v. TAU for total psychotic symptoms (PANSS), subjective recovery from psychosis, PTSD symptoms, depression, anxiety, and general health status. Signals of efficacy at 12-month were less pronounced but remained robust for PTSD symptoms and general health status. Conclusions The trial feasibility criteria were fully met, and EMDRp was associated with promising signals of efficacy on a range of valuable clinical outcomes. A larger-scale, multi-center trial of EMDRp is feasible and warranted.