In this work, we tested ab initio methods combined with evolutionary algorithms for searching stable crystalline structures for solid fluorine in the Tera-Pascal (TPa) regime. We performed several structural searches using the USPEX code, at pressures that spanned the range from 1 to 5 TPa, considering up to 16 atoms per unit-cell for selected pressures. Our findings partially support recent studies by validating the transformation of fluorine from a molecular form, Cmca, into an intermediate polymeric form before its eventual dissociation. Enthalpy comparisons between candidate structures of fluorine at high pressure show a direct transition from the molecular phase Cmca into a Pm¯3n extended structure at 2.7 TPa, the later consisting of linear chains and independent atoms, which disagrees with previous conflicting reports that proposed two other intermediate phases to also exist as stable crystalline forms close to 3 TPa at zero temperature.