The μ Arae planetary system is fairly complex, because it contains two already known planets, Arae b with P=640 days and Arae c with P=9.64 days , and a third companion on a wide, but still poorly defined, orbit. Even with three planets in the system, the data points keep anomalously high dispersion around the fitted solution. The high residuals are only partially due to the strong p-mode oscillations of the host star. We therefore studied the possible presence of a fourth planet in this system. During the past years we carried out additional and extremely precise radial-velocity measurements with the HARPS spectrograph. These data turned out to be highly important for constraining the many free parameters in a four-planet orbital fit. Nevertheless, the search for the best solution remains difficult in this complex and multi-dimensional parameter space. The new Stakanof software, that uses an optimized genetic algorithm, helped us considerably in this task and made our search extremely efficient and successful. We provide a full orbital solution of the planetary system around Arae. It turns out to be the second system known to harbor 4 planetary companions. Before this study, Arae b was already well known and characterized. Thanks to the new data points acquired with HARPS we can confirm the presence of Arae c at P=9.64 days, which produces a coherent RV signal over more than two years. The new orbital fit sets the mass of Arae c to 10.5 . Furthermore, we present the discovery of Arae d , a new planet on an almost circular 310 day-period and with a mass of 0.52 . Finally, we give completely new orbital parameters for the longest-period planet, Arae e . It is the first time that this companion has been constrained by radial-velocity data into a dynamical stable orbit, which leaves no doubt about its planetary nature. We take this opportunity to discuss naming conventions for poorly characterized planets.