The growth of aviation industry in Indonesia accelerates the escalation of Airport Gate Assignment Problem in the Soekarno Hatta International Airport. The gate assignment issue mainly influence passenger satisfaction over the general flight service. This research was conducted to develop Gate Assignment Optimization in the Soekarno Hatta International Airport, focused on minimizing the number of Un-gated Flights. This paper propose a meta-heuristic approximation approach namely simulated annealing to solve the Gate Assignment Problem. Output of this paper is the aircraft Gate Assignment Order at Terminal 2 Soekarno Hatta International Airport. The result suggests, decreasing number of Un-gated Flights occurred with the implementation of the proposed method. This research may be developed in the future by adding another objective function such as minimizing passenger walking distance and constructing real time based model.