The classification of retinal vessels into arterioles and venules is important for any automated system for the detection of vascular changes in the retina and for the discovery of biomarkers associated with systemic diseases such as diabetes, hypertension, and cardiovascular disease. We introduce Squared-loss Mutual Information clustering (SMIC) for classifying arterioles and venules in retinal images for the first time (to the best of our knowledge). We classified vessels from 70 fundus camera images using only 4 colour features in zoneB(802 vessels) and in an extended zone (1,207 vessels).We achieved an accuracy of 90.67 and 87.66%in zoneBand the extended zone, respectively. We further validated our algorithm by classifying vessels in zone B from two publically available datasets—INSPIRE-AVR (483 vessels from 40 images) and DRIVE (171 vessels from 20 test images). The classification rates obtained on INSPIRE-AVR and DRIVE dataset were 87.6 and 86.2%, respectively. We also present a technique to sort the unclassified vessels which remained unlabeled by the SMIC algorithm.