Heart failure (HF) is a major cardiovascular disease worldwide, and the early detection and diagnosis remain challenges. Recently, heart rhythm complexity analysis, derived from non-linear heart rate variability (HRV) analysis, has been proposed as a non-invasive method to detect diseases and predict outcomes. In this study, we aimed to investigate the diagnostic value of heart rhythm complexity in HF patients. We prospectively analyzed 55 patients with symptomatic HF with impaired left ventricular ejection fraction and 97 participants without HF symptoms and normal LVEF as controls. Traditional linear HRV parameters and heart rhythm complexity including detrended fluctuation analysis (DFA) and multiscale entropy (MSE) were analyzed. The traditional linear HRV, MSE parameters and DFAα1 were significantly lower in HF patients compared with controls. In regression analysis, DFAα1 and MSE scale 5 remained significant predictors after adjusting for multiple clinical variables. Among all HRV parameters, MSE scale 5 had the greatest power to differentiate the HF patients from the controls in receiver operating characteristic curve analysis (area under the curve: 0.844). In conclusion, heart rhythm complexity appears to be a promising tool for the detection and diagnosis of HF.