The increase in air traffic, forces the current centralized air traffic control systems to be replaced with more decentralized control systems. The idea of free flight is developed with this consideration. In free flight aircrafts communicate and cooperate with each other to solve the conflicts. Each aircraft has its own separate optimization criteria, and aircrafts have to modify their paths considering these criteria. There should be a compromise in the amount of concession that aircrafts make in order to solve the conflict. In this research negotiation is introduced to achieve an agreement on the deviations from the optimal paths. Aircrafts negotiate on the amount of deviations they will perform to modify their paths. A frame for negotiation is developed, negotiation principles are determined, and simulations are performed.