MiRNA-disease association prediction plays an important role in identifying human disease-related miRNAs. This approach is helpful not only to formulate individualized diagnosis schemes, but also to understand the pathogenesis of diseases. Many studies have focused on enhancing the prediction performance using explicit side information, such as miRNA functional similarity and disease semantic similarity. The existing approaches, however, often ignore the higher-order implicit proximity among miRNAs and diseases. To this end, in this paper, we first propose a novel approach HOP_MDA (Higher-Order Proximity based MiRNA and Disease Association Prediction) for predicting potential association between miRNA and disease. Both explicit interaction information and implicit higher-order proximity information between miRNA and disease are encoded with different order proximity matrices which are weightily combined into a parameterized prediction matrix. A supervised learning approach based on the known miRNAs-disease associations is proposed to determine the optimal weight parameters. The prediction matrix is then used to achieve effective prediction. Additionally, a higher-order proximity approximation technique (HOPA_MDA) is presented to make more efficient predictions. 5-fold cross validation is used to evaluate the performance of our proposed method. The average AUC values of HOPA_MDA for two real datasets are 0.921+/-0.002 and 0.944+/-0.0015, respectively. Our method can also predict potential miRNAs specific to new diseases with no known related miRNAs.