Large-scale multiple testing, which calls for tens of thousands of hypothesis testings simultaneously, has been applied in many scientific fields. Conventional multiple testing procedures often focused on the control of false discovery rate (FDR) and largely ignored covariate information and the dependence structure among tests. In this paper, we propose an FDR control procedure, termed as Covariate-Modulated Local Index of Significance (cmLIS) procedure, for large-scale multiple testing. The cmLIS procedure not only takes into account local correlations among tests but also accommodates the covariate information by leveraging a covariate-modulated hidden Markov model (HMM). In the oracle case that all parameters of the covariate-modulated HMM are known, we show that the cmLIS procedure is valid and optimal in some sence. According to whether the number of mixed components in the non-null distribution is known, we provide two Bayesian sampling algorithms for parameter estimation. Extensive simulations are conducted to demonstrate the effectiveness of the cmLIS procedure over state-of-the-art multiple testing procedures. Finally, we apply the cmLIS procedure to dosage response data.