We aimed to discover novel associations between leptin and circulating proteins which could link leptin to the development of cardiovascular disease in patients with type 2 diabetes (T2DM). In a discovery phase, we investigated associations between 88 plasma proteins, assessed with a proximity extension assay, and plasma leptin in a cohort of middle-aged patients with T2DM. Associations passing the significance threshold of a False discovery rate of 5% (corresponding to p < 0.0017) were replicated in patients with T2DM in an independent cohort. We also investigated if proteins mediated the longitudinal association between plasma leptin and the incidence of major cardiovascular events (MACE). One protein, adipocyte fatty acid binding protein (A-FABP), was significantly associated with leptin in both the discovery phase [95% CI (0.06, 0.17) p = 0.00002] and the replication cohort [95% CI (0.12, 0.39) p = 0.0003]. Multiplicative interaction analyses in the two cohorts suggest a stronger association between A-FABP and leptin in men than in women. In longitudinal analyses, the association between leptin and MACE was slightly attenuated after adding A-FABP to the multivariate model. Our analysis identified a consistent association between leptin and A-FABP in two independent cohorts of patients with T2DM, particularly in men.Trial registration: ClinicalTrials.gov identifier NCT01049737.