Heart rate variability (HRV) is reduced in diabetes mellitus (DM) patients, suggesting dysfunction of cardiac autonomic regulation which has been associated with increased risk for pathological cardiac events. In this paper, we examined changes in HRV complexity in association to blood glucose level (BGL) and duration of diabetes. Resting HRV and BGL measurements of 32 healthy controls and 54 type 2 DM (T2DM) patients were analyzed. HRV complexity was assessed using Shannon entropy, sample entropy (SampEn), multiscale entropy (MSE), and multiscale Renyi entropy. HRV complexity increased with hyperglycemia indicated by increases in Shannon entropy and MSE and decreases in Renyi entropy for negative orders. Diabetes duration was strongly associated with Renyi entropy which increased for positive orders and decreased for negative orders as a function of disease duration. Shannon entropy, SampEn and MSE did not correlate with disease duration.