Aims: This study aimed to determine the trajectory of diabetic vascular diseases and to investigate the association between vascular diseases and dementia. Methods: We included adults aged ≥ 50 years with newly diagnosed type 2 diabetes (n = 173,118) from 2001 to 2005 who were followed-up until December 31, 2013 in the Taiwan’s National Health Insurance Research Database. Multivariable Cox regression models were constructed to estimate hazard ratios (HRs) and confidence limits (CLs) for all-cause dementia in relation to the number, types, and occurrence patterns of vascular disease. Results: Within 1 year of diabetes diagnosis, 26.3% of adults developed their first vascular disease. During the 1,864,279 person-years of follow-up, 17,426 adults had all-cause dementia, corresponding to an incidence of 97.9 cases/10,000 person-years in 127,718 adults with at least one vascular disease and 67.5 cases/10,000 person-years in 45,400 adults without vascular diseases. Across all age groups, adults who subsequently developed a vascular disease in two one-year windows since diabetes diagnosis had the highest incidence of all-cause dementia. In comparison with adults without vascular diseases, HR for all-cause dementia was 1.99 (CL: 1.92–2.07) for those with one vascular disease only; 2.04 (CL: 1.98–2.13) for two or more vascular diseases; 3.56 (CL: 3.44–3.70) for stroke only; and 2.06 (CL: 1.99–2.14) for neuropathy alone. Similar associations were also observed with a smaller magnitude for adults with nephropathy, retinopathy, cardiovascular disease, or peripheral arterial disease. Conclusions: Patients with diabetes-related complications, particularly stroke and neuropathy, and those with rapidly developed vascular diseases appeared to have a high risk of dementia.