The development of mobile edge computing (MEC) is accelerating the popularity of 5G applications. In the 5G era, aiming to reduce energy consumption and latency, most applications or services are conducted on both edge cloud servers and cloud servers. However, the existing multi-cloud composition recommendation approaches are studied in the context of resources provided by a single cloud or multiple clouds. Hence, these approaches cannot cope with services requested by the composition of multiple clouds and edge clouds jointly in MEC. To this end, this paper firstly expands the structure of the multi-cloud service system and further constructs a multi-cloud multi-edge cloud (MCMEC) environment. Technically, we model this problem with formal concept analysis (FCA) by building the service–provider lattice and provider–cloud lattice, and select the candidate cloud composition that satisfies the user’s requirements. In order to obtain an optimized cloud combination that can efficiently reduce the energy consumption, money cost, and network latency, the skyline query mechanism is utilized for extracting the optimized cloud composition. We evaluate our approach by comparing the proposed algorithm to the random-based service composition approach. A case study is also conducted for demonstrating the effectiveness and superiority of our proposed approach.