Cuckoo Search (CS) is one of the most recent population-based metaheuristics. CS algorithm is based on the cuckoo’s behavior and the mechanism of Lévy flights. The Binary Cuckoo Search algorithm (BCS) is new discrete version used to solve binary optimization problem based on sigmoid function. In this paper, we propose a new cuckoo search for binary multiobjective optimization. Pareto dominance is used to find optimal pareto solutions. Computational results on some bi-criteria knapsack instances show the effectiveness of the proposed algorithm and its ability to achieve good quality solutions.