In recent years, emerging evidence has shown that long noncoding RNAs (lncRNAs) have important roles in the biological processes of complex diseases. However, experiments to determine the associations between diseases and lncRNAs are time consuming and costly. Therefore, there is a need to develop effective computational methods for exploring potential lncRNA-disease associations. In this study, we present a computational prediction method based on high-order proximity and matrix completion to predict lncRNA-disease associations (HOPMCLDA). HOPMCLDA integrates explicit similarity and high-order proximity information on lncRNAs and diseases and constructs a heterogeneous disease-lncRNA network to utilize similarity information. Finally, nuclear norm regularization is carried out on the heterogeneous network for the recovery of a lncRNA-disease association matrix. By implementing leave-one-out cross validation (LOOCV) and five-fold cross validation (5-fold CV), we compare HOPMCLDA with five other methods. HOPMCLDA outperforms the other methods, with area under the receiver operating characteristic curve values of 0.8755 and 0.8353 ± 0.0045 using LOOCV and 5-fold CV, respectively. Furthermore, case studies of three human diseases (gastric cancer, osteosarcoma, and hepatocellular carcinoma) confirm the reliable predictive performance of HOPMCLDA.