A superhydrophobic composite coating consisting of polytetrafluoroethylene (PTFE) and poly(acrylic acid)+ β-cyclodextrin (PAA + β-CD) was prepared on an aluminum alloy AA 6061T6 substrate by a three-step process of electrospinnig, spin coating, and electrospraying. The electrospinning technique is used for the fabrication of a polymeric binder layer synthesized from PAA + β-CD. The superhydrophilic characteristic of the electrospun PAA + β-CD layer makes it suitable for the absorption of an aqueous suspension with PTFE particles in a spin-coating process, obtaining a hydrophobic behavior. Then, the electrospraying of a modified PTFE dispersion forms a layer of distributed PTFE particles, in which a strong bonding of the particles with each other and with the PTFE particles fixed in the PAA + β-CD fiber matrix results in a remarkable improvement of the particles adhesion to the substrate by different heat treatments. The experimental results corroborate the important role of obtaining hierarchical micro/nano multilevel structures for the optimization of superhydrophobic surfaces, leading to water contact angles above 170°, very low contact angle of hysteresis (CAH = 2°) and roll-off angle (αroll−off < 5°). In addition, a superior corrosion resistance is obtained, generating a barrier to retain the electrolyte infiltration. This study may provide useful insights for a wide range of applications.