This paper presents a codebook-based speech enhancement algorithm by using Markov process and speech-presence probability (SPP). The Markov process is utilized to model the correlation between the adjacent code-vectors in the codebook for optimizing Bayesian minimum mean squared error (MMSE) estimator. Then the proposed estimator is used to estimate spectral shapes and gains of speech and noise. The correlation between adjacent linear prediction (LP) gains is also fully considered during the procedure of parameter estimation. Through the introduction of SPP in the codebook-constrained Wiener filter, the proposed Wiener filter achieves the goal of much more noise reduction and does not result in the speech component distortion. The evaluation results confirm that the proposed algorithm has a much better performance for reducing annoying background noise than the conventional codebook-based algorithms.