Brewer's conjecture, and its resulting formalization as the CAP theorem, impose serious limitations on the consistency, availability and network partitioning tolerance characteristics of distributed systems. Despite its importance however, few works explicitly consider the implications of the CAP theorem in the design of applications, especially for applications that are designed natively for the Cloud. In order to address this need, in this work we propose a CAP-oriented design methodology for Cloud-native applications. For this purpose we build and extend our previous work on Cloud architectural patterns. Finally, we show how the methodology can be used in practice to design an application solution with desired CAP properties.