In this paper we present MEDEA, an execution model for automatically executing programs, written in various programming languages, portably over disparate cloud fabrics. MEDEA abstract away the details of cloud-based program execution by providing language support (to enable applications to be programmatically described) as well as runtime support that abstracts away implementation-specific details of cloud-based queuing, compute, and storage services. To facilitate cross-cloud portability, MEDEA plugs a wide range of compute, storage, and FIFO queue offerings into this system, including those provided by Amazon Web Services, Microsoft Azure, Google App Engine, and AppScale. By doing so, MEDEA relieves developers of the burden of having to become experts with each cloud system on which they wish to run. To investigate the potential of MEDEA, we employ the system for a number of different use cases in which we compare and contrast the different plugins in terms of price and performance using different applications, domains, and programming languages.