Cloud computing has heralded many advantages including self-service, elasticity, pay as you go, improved accessibility to computation resources, and ease of deployment and deployment automation. However, to extend those advantages to a larger audience, higher-level abstractions such as Software as a Service (SaaS) or Platform as a Service (PaaS) are needed. This paper presents Stratos, which is a Platform-as-a-Service based around the principles and design of Service Oriented Architecture (SOA). Furthermore, we introduce the concept of Cloud Native attributes, which we argue are properties essential to extend the benets of the underlying Cloud to PaaS and SaaS users. We present Stratos as a Cloud Native PaaS oering, discuss the architecture that enables Cloud Native attributes, and discuss scenarios where Stratos can be useful to the end user.