With the increasing incidence of cerebrovascular diseases and dementia, considerable efforts have been made to develop effective treatments on vascular cognitive impairment (VCI), among which accumulating practice-based evidence has shown great potential of the traditional Chinese medicine (TCM). Current randomized double-blind controlled trial has been designed to evaluate the 6-month treatment effects of Dengzhan Shengmai (DZSM) capsules, one TCM herbal preparations on VCI, and to explore the underlying neural mechanisms with graph theory-based analysis and machine learning method based on diffusion tensor imaging (DTI) data. A total of 82 VCI patients were recruited and randomly assigned to drug (45 with DZSM) and placebo (37 with placebo) groups, and neuropsychological and neuroimaging data were acquired at baseline and after 6-month treatment. After treatment, compared to the placebo group, the drug groups showed significantly improved performance in Alzheimer's Disease Assessment Scale-Cognitive subscale (ADAS-cog) score (p < 0.001) and the other cognitive domains. And with the reconstruction of white matter structural network, there were more streamlines connecting the left thalamus and right hippocampus in the drug groups (p < 0.001 uncorrected), with decreasing nodal efficiency of the right olfactory associated with slower decline in the general cognition (r = 0.364, p = 0.048). Moreover, support vector machine classification analyses revealed significant white matter network alterations after treatment in the drug groups (accuracy of baseline vs. 6-month later, 68.18 %). Taking together, the present study showed significant efficacy of DZSM treatment on VCI, which might result from white matter microstructure alterations and the topological changes in brain structural network.