The cloud-based solutions can be also applied on e-Health services. To analyze it we have researched several publications about the implementation of some e-Health services based on the Cloud mainly through Medline. In this paper, concepts of Cloud Computing and mobile health records systems are explained. Moreover, the benefits, constraints, issues and requisites of a Mobile Health Record System implemented on the Cloud are analyzed. The mobility and sharing that Cloud-based solutions provide is one of main advantages, but there are some barriers like the security that must be overcome. Cloud Computing is still a technology under development, which means that in a near future the services it offers us will be greater.