Given an increasing number of cloud services available in the market, evaluating candidate cloud services is crucial and beneficial for both service customers (e.g. cost-benefit analysis) and providers (e.g. direction of improvement). When it comes to performing any evaluation, a suitable methodology is inevitably required to direct experimental implementations. Nevertheless, there is still a lack of a sound methodology to guide the evaluation of cloud services. By borrowing the lessons from evaluation of traditional computing systems, referring to the guidelines for Design Of Experiments (DOE), and summarizing the existing experiences of real experimental studies, the authors proposed a generic methodology for cloud services evaluation.