We perform an extensive numerical study of the effects of clustering on the structural properties of complex networks. We observe that strong clustering in heterogeneous networks induces the emergence of a core-periphery organization that has a critical effect on their percolation properties. In such situation, we observe a novel double phase transition, with an intermediate phase where only the core of the network is percolated, and a final phase where the periphery percolates regardless of the core. Interestingly, strong clustering makes simultaneously the core more robust and the periphery more fragile. These phenomena are also found in real complex networks.