With the increasingly busy transportation of cargo at container terminals (CTs), the requirements for terminal throughput and operational efficiency are constantly increasing. The operational efficiency and cost of CTs are closely related to the seamless docking of terminal facilities, especially the joint operation between berths and quay cranes (QCs). Therefore, a joint allocation problem of berths and QCs (BACASP) is presented in this paper and formalized as a mathematical model to minimize terminal operation costs and shipowner dissatisfaction. Given that BACASP is an NP-hard problem, an improved multi-objective cuckoo search (IMOCS) algorithm is proposed to solve this problem, in which an elite-guided tangent flight strategy is presented to speed up the convergence for making up the lack of random search direction of the traditional cuckoo search algorithm; and an information-enhanced abandonment strategy is put forward to increase the possibility of escaping from local optima. Numerical experimental results show the effectiveness of the proposed algorithm.