We study the role of contingent convertible bonds (CoCos) in a complex network of interconnected banks. By studying the system's phase transitions, we reveal that the structure of the interbank network is of fundamental importance for the effectiveness of CoCos as a financial stability enhancing mechanism. Our results show that, under some network structures, the presence of CoCos can increase (and not reduce) financial fragility, because of the occurring of unneeded triggers and consequential suboptimal conversions that damage CoCos investors. We also demonstrate that, in the presence of a moderate financial shock, lightly interconnected financial networks are more robust than highly interconnected networks. This makes them a potentially optimal choice for both CoCos issuers and buyers.