The continuing growth of air traffic worldwide motivates the need for new approaches to air traffic management that are more flexible both in terms of traffic volume and weather. Free Flight is one such approach seriously considered by the aviation community. However the benefits of Free Flight are severely curtailed in the convective weather season when weather is highly active, leading aircrafts to deviate from their optimal trajectories. This paper investigates the use of ant colony optimization in generating optimal weather avoidance trajectories in Free Flight airspace. The problem is motivated by the need to take full advantage of the airspace capacity in a Free Flight environment, while maintaining safe separation between aircrafts and hazardous weather. The experiments described herein were run on a high fidelity Free Flight air traffic simulation system which allows for a variety of constraints on the computed routes and accurate measurement of environments dynamics. This permits us to estimate the desired behavior of an aircraft, including avoidance of changing hazardous weather patterns, turn and curvature constraints, and the horizontal separation standard and required time of arrival at a pre determined point, and to analyze the performance of our algorithm in various weather scenarios. The proposed Ant Colony Optimization based weather avoidance algorithm was able to find optimum weather free routes every time if they exist. In case of highly complex scenarios the algorithm comes out with the route which requires the aircraft to fly through the weather cells with least disturbances. All the solutions generated were within flight parameters and upon integration with the flight management system of the aircraft in a Free Flight air traffic simulator, successfully negotiated the bad weather.