Objective Long non-coding RNAs (lncRNAs) participate in a variety of vital biological processes and closely relate with various human diseases. The prediction of lncRNA-disease associations can help to understand the mechanisms of human disease at the molecular level, and also contribute to diagnosis and treatment of diseases. Most existing methods of predicting the lncRNA-disease associations ignore the deep embedding features hiding in lncRNA/disease network topological structures. Moreover, randomly selecting the negative samples will affect the robustness of predictors.Methods Here we first set up a high quality dataset by using an effective strategy to select the negative samples (i.e., pairs of non lncRNA-disease association) with relatively higher quality instead of randomly selecting the negative samples, then proposed a novel method (called NELDA) to predict the potential lncRNA-disease associations by building 4 deep auto-encoder models to learn the low dimensional network embedding features from the lncRNA/disease similarity networks, and lncRNA-disease association network, respectively. NELDA takes the lncRNA/disease similarity network embedding features as the input of one support vector machine (SVM) classifier, and the lncRNA/disease association network embedding features as the input of another SVM classifier. The prediction results of these two SVM classifiers are fused by the weighted average strategy to obtain the final prediction results.Results In 10-fold cross-validation (10 CV) test, the AUC of NELDA achieves 0.982 7 on high quality dataset, which is 0.062 7 and 0.020 7 higher than that of other two state-of-the-art methods of LDASR and LDNFSGB, respectively. In the case studies of stomach cancer and breast cancer, 29/40 (72.5%) novel predicted lncRNAs associated with stomach and breast cancers are supported by recent literatures and public datasets.Conclusion These experimental results demonstrate that NELDA is a superior method for predicting the potential lncRNA-disease associations. It has the ability to discover the new lncRNA-disease associations.