In recent years, cloud computing has become a promising solution for decreasing the deployment and maintenance costs of Internet services. To provide Internet application service by using cloud resource, a service provider needs to consider the resource subscription cost and Service Level Agreement (SLA) of its users. Several kinds of pricing model of cloud resource subscription have been proposed. In such case, the Internet service provider plays the role of a cloud customer with a need of optimal cloud resource subscription policy to reduce its operation cost. Therefore, how to determine a suitable policy of cloud resource subscription has become a challenging issue. In this work, we proposed a two-phase approach to solve the cloud resource subscription problem. The first phase considered long-term resource reservation. In this phase, we proposed a mathematic model to compute an upper bound of the optimal amount of long-term reserved resource. The second phase was dynamic resource subscription phase. In order to overcome dynamic resource demand, in this phase, we used Hidden Markov Model (HMM) to predict resource demand and allocate VM resource adaptively based on the prediction. We evaluated our solution using real-world resource demand data. Our numerical results indicated that our approach can reduce the cost of cloud resource subscription significantly.