Calculations of fluorine binding and migration on carbon nanotube surfaces show that fluorine forms varying surface superlattices at increasing temperatures. The ordering transition is controlled by the surface migration barrier for fluorine atoms to pass through next neighbor sites on the nanotube, explaining the transition from semi-ionic low coverage to covalent high coverage fluorination observed experimentally for gas phase fluorination between 200 and 250 degrees C. The effect of solvents on fluorine binding and surface diffusion is explored.