The implementation phase of cloud-based Enterprise Resource Planning (ERP) has received considerable interest from industry because of its effectiveness and potential for cost reduction compared with traditional ERP. This study investigates the challenges through four stages of cloud-based ERP implementation namely: realisation, development, assertion, and cutover. The literature includes some studies on the challenges of cloud ERP, but none of them has tried to distinguish between the challenges for each particular stage. This means that for each stage there are specific challenges that could just occur during that individual stage, or be repeated in other stages. Understanding the challenges during the four stages of implementation enables the awareness of the probability of occurrence of each challenge in order to mitigate them.