Superhydrophobic surfaces were fabricated with a high water contact angle (CA) of 155° and a low CA hysteresis of 3°. This is achieved by covering the substrate with carbon-based microstructures that take the shape of flowers. These structures, synthesized by pulsed magnetron discharge from acetylene, are confirmed to be fractal by the box-counting determination method. The deposition method is simple, effective, environmentally friendly and applicable to industrial processes involving large flat substrates, like those in the steel and glass coating industries. This work highlights the importance of the surface density of fractal structures for the fabrication of superhydrophobic surfaces. To have a high water CA (>150°), the number of fractal structures per cm on a given surface must be as high as possible. If this number decreases, an additional fluorine treatment is necessary to obtain superhydrophobic films.