The functional airspace block (FAB) concept is adopted by European airspace to allow cooperation between airspace users to manage the air traffic flow, while ensuring efficiency, safety, and fairness without the constraints of geographical boundaries. This integration of airspaces allows for flexibility in airspace management and aircraft trajectory planning. This paper proposes a distributed air traffic flow management model to address fourdimensional trajectory planning over the European FAB. The proposed method is based on a metaheuristic approach that uses a hybrid algorithm of simulated annealing and hill-climbing local search to separate a given set of aircraft trajectories in space and time domain (termed as flight interaction), by allocating an alternative flight plan (route and departure time) to each flight. An innovative data structure, termed as FAB–flight interaction matrix, captures the flight interaction information between and within FABs. The proposed distributed model is implemented and tested with two air traffic data sets comprising 4000 flights (3 h traffic) and 26,000 flights (one full day traffic data over the European airspace). The performance of the model is then compared with a centralized air traffic flow management model on scalability and interaction minimization. Results indicates that, though both approaches were able to achieve interaction-free trajectory planning within computational time acceptable for the operational context, the distributed model converges faster to an interaction-free solution as traffic size increases, which shows the viability of the distributed model for effective FAB implementation.