Graphical abstractDisplay Omitted HighlightsA Mobile Network Deployment Problem is tackled using the CRO.The Coral Reefs Optimization is based on corals and corals reefs biology.A full description of the new algorithm is carried out.Experimental comparison with alternative soft-computing algorithms is done. In this paper we apply a novel meta-heuristic approach, the Coral Reefs Optimization (CRO) algorithm, to solve a Mobile Network Deployment Problem (MNDP), in which the control of the electromagnetic pollution plays an important role. The CRO is a new bio-inspired meta-heuristic algorithm based on the growing and evolution of coral reefs. The aim of this paper is therefore twofold: first of all, we study the performance of the CRO approach in a real hard optimization problem, and second, we solve an important problem in the field of telecommunications, including the minimization of electromagnetic pollution as a key concept in the problem. We show that the CRO is able to obtain excellent solutions to the MNDP in a real instance in Alcala de Henares (Madrid, Spain), improving the results obtained by alternative algorithms such as Evolutionary, Particle Swarm Optimization or Harmony Search algorithms.