Background: Tumour growth is accompanied by gene and/or protein changes that may lead to peroxidation of the cell membrane species and, hence, to the emission of volatile organic compounds (VOCs). In this study, we investigated the ability of a nanosensor array to discriminate between breath VOCs that characterise healthy states and the most widespread cancer states in the developed world: lung, breast, colorectal, and prostate cancers. Methods: Exhaled alveolar breath was collected from 177 volunteers aged 20–75 years (patients with lung, colon, breast, and prostate cancers and healthy controls). Breath from cancerous subjects was collected before any treatment. The healthy population was healthy according to subjective patient's data. The breath of volunteers was examined by a tailor-made array of cross-reactive nanosensors based on organically functionalised gold nanoparticles and gas chromatography linked to the mass spectrometry technique (GC-MS). Results: The results showed that the nanosensor array could differentiate between ‘healthy' and ‘cancerous' breath, and, furthermore, between the breath of patients having different cancer types. Moreover, the nanosensor array could distinguish between the breath patterns of different cancers in the same statistical analysis, irrespective of age, gender, lifestyle, and other confounding factors. The GC-MS results showed that each cancer could have a unique pattern of VOCs, when compared with healthy states, but not when compared with other cancer types. Conclusions: The reported results could lead to the development of an inexpensive, easy-to-use, portable, non-invasive tool that overcomes many of the deficiencies associated with the currently available diagnostic methods for cancer.