Single- and few-layer black phosphorus possesses interesting properties suitable for various optoelectronic applications where graphene cannot be applied due to its vanishing band gap. As phosphorene tends to degrade in environments, various approaches including fluorination have been explored to passivate its surface. Several structures of fluorinated phosphorene have thus recently been reported to demonstrate this approach. On the basis of a combination of first-principles electronic structure calculations and ab initio molecular dynamics, we reconsider the structure of fluorinated phosphorene marking previously reported configurations as thermodynamically unstable with a tendency to decompose spontaneously. We reveal the mechanism of fluorination and propose novel thermodynamically and energetically stable structures containing double fluorine units with enhanced antioxidative stability caused by the fluorination-induced negative electrostatic potential on the surface of phosphorene. The partially fluorinated structure demonstrates almost the same band gap compared to bare phosphorene, making it possible to utilize them in nano-optoelectronic applications.