Early in the course of psychosis, alterations in brain connectivity accompany the emergence of psychiatric symptoms and cognitive impairments, including processing speed. The clinical-staging model is a refined form of diagnosis that places the patient along a continuum of illness conditions, which allows stage-specific interventions with the potential of improving patient care and outcome. This cross-sectional study investigates brain connectivity features that characterize the clinical stages following a first psychotic episode. Structural brain networks were derived from diffusion-weighted MRI for 71 early-psychosis patients and 76 healthy controls. Patients were classified into stage II (first-episode), IIIa (incomplete remission), IIIb (one relapse), and IIIc (two or more relapses), according to the course of the illness until the time of scanning. Brain connectivity measures and diffusion parameters (fractional anisotropy, apparent diffusion coefficient) were investigated using general linear models and sparse linear discriminant analysis (sLDA), studying distinct subgroups of patients who were at specific stages of early psychosis. We found that brain connectivity impairments were more severe in clinical stages following the first-psychosis episode (stages IIIa, IIIb, IIIc) than in first-episode psychosis (stage II) patients. These alterations were spatially diffuse but converged on a set of vulnerable regions, whose inter-connectivity selectively correlated with processing speed in patients and controls. The sLDA suggested that relapsing-remitting (stages IIIb, IIIc) and non-remitting (stage IIIa) patients are characterized by distinct dysconnectivity profiles. Our results indicate that neuroimaging markers of brain dysconnectivity in early psychosis may reflect the heterogeneity of the illness and provide a connectomics signature of the clinical-staging model.