Psychiatric diagnosis is inherently difficult, due to the lack of clear biomarkers or any other objective assessment. Although quantitative, the psychometric scales employed during the psychiatric interview are subjective, so psychiatrists are required to undergo extensive training before they are properly qualified to diagnose. In search of objective, quantitative insight into the structure of psychotic speech, we applied standard techniques in the field of complex networks to measure speech graph attributes in chronic patients with schizophrenia, bipolar disorder type I, and non-psychotic controls as they reported waking and dream contents. Speech graphs are simply directed graphs of word trajectories, upon which graph-theoretical measures can be applied. We show that the three different groups can be sorted just by looking at a handful of speech graph attributes, after discarding all semantic content. The technique can also be successfully extended to patients during their first clinical contact, objectively classifying diagnosis 6 months in advance and providing a diagnostic-independent “disorganization index” for speech. The results demonstrate the feasibility of the differential diagnosis of psychosis based on the analysis of speech graphs, pointing to a fast, low-cost and language-invariant tool for psychiatric diagnosis and the objective search for biomarkers.