Air cargo in Indonesia began to grow in line with the beginnings of a national airline and economic growth in the region. Cargo growth is also driven by the increasingly competitive business competition that need of times faster and on time product delivery. Aspects of service time in this study performed at the service of domestic cargo warehouse operator PT Garuda Indonesia Cargo and PT Gapura Angkasa on Domestic Cargo Terminal Soekarno-Hatta Airport. Research user perceptions on the dimensions of quality of service time necessary to gain insight about the cargo services that is important for role in the distribution of goods. Queuing theory approach can be used to give an idea about the amount of time waiting in the queue system. The minimum service time is the minimum time appropriate user expectations. This study uses three (3) scenarios to calculate the minimum service time. Based on the analysis results can be known the time of service with queuing theory approach to the warehouse operator PT Garuda Indonesia and PT Gapura Angkasa is 38.10 minutes and 41.27 minutes. The minimum service time at PT Garuda Indonesia Cargo with scenario 1 2 and 3 is 31.30 34.90 and 29.49 minutes. The minimum service time at the PT Gapura Angkasa with scenario 1 2 and 3 is 33.30 37.90 and 31.04 minutes. The minimum service time of user expectations can be achieved by adding the resources ( personnel and equipment / machinery ) according to the need for both warehouse operators.