Cloud services permit healthcare providers to ensure information handling and allow different service resources such as Software as a Service (SaaS), Platform as a Service (PaaS) and Infrastructure as a Service (IaaS) on the Internet, given that security and information proprietorship concerns are attended to. Health Care Providers (HCPs) in Nigeria however, have been confronted with various issues because of their method of operations. Amongst the issues are ill-advised methods of data storage and unreliable nature of patient medical records. Apart from these challenges, trouble in accessing quality healthcare services, high cost of medical services, and wrong analysis and treatment methodology are not left out. Cloud Computing has relatively possessed the capacity to give proficient and reliable method for securing medical information and the need for data mining tools in this form of distributed system will go a long way in achieving the objective set out for this project. The aim of this research therefore is to implement a cloud-based architecture that is suitable to integrate Healthcare Delivery into the cloud to provide a productive mode of operation. The proposed architecture consists of four phases (4-Tier); a User Authentication and Access Control Engine (UAACE) which prevents unauthorized access to patient medical records and also utilizes standard encryption/decoding techniques to ensure privacy of such records. The architecture likewise contains a Data Analysis and Pattern Prediction Unit (DAPPU) which gives valuable data that guides decision making through standard Data mining procedures as well as Cloud Service Provider (CSP) and Health Care Providers (HCPs). The architecture which has been implemented on CloudSim has proved to be efficient and reliable base on the results obtained when compared with previous work.