The coati optimization algorithm (COA) is a recently proposed heuristic algorithm. The COA algorithm, which solved the continuous optimization problems in its original paper, has been converted to a binary optimization solution by using transfer functions in this paper. Thus, binary COA (BinCOA) is proposed for the first time in this study. In this study, twenty transfer functions are used (four S-shaped, four V-shaped, four Z-shaped, four U-shaped, and four taper-shaped transfer functions). Thus, twenty variations of BinCOA are obtained, and the effect of each transfer function on BinCOA is examined in detail. The knapsack problem (KP) and uncapacitated facility location problem (UFLP), which are popular binary optimization problems in the literature, are chosen to test the success of BinCOA. In this study, small-, middle-, and large-scale KP and UFLP datasets are selected. Real-world problems are not always low-dimensional. Although a binary algorithm sometimes shows superior success in low dimensions, it cannot maintain the same success in large dimensions. Therefore, the success of BinCOA has been tested and demonstrated not only in low-dimensional binary optimization problems, but also in large-scale optimization problems. The most successful transfer function is T3 for KPs and T20 for UFLPs. This showed that S-shaped and taper-shaped transfer functions obtained better results than others. After determining the most successful transfer function for each problem, the enhanced BinCOA (EBinCOA) is proposed to increase the success of BinCOA. Two methods are used in the development of BinCOA. These are the repair method and the XOR gate method. The repair method repairs unsuitable solutions in the population in a way that competes with other solutions. The XOR gate is one of the most preferred methods in the literature when producing binary solutions and supports diversity. In tests, EBinCOA has achieved better results than BinCOA. The added methods have proven successful on BinCOA. In recent years, the newly proposed evolutionary mating algorithm, fire hawk optimizer, honey badger algorithm, mountain gazelle optimizer, and aquila optimizer have been converted to binary using the most successful transfer function selected for KP and UFLP. BinCOA and EBinCOA have been compared with these binary heuristic algorithms and literature. In this way, their success has been demonstrated. According to the results, it has been seen that EBinCOA is a successful and preferable algorithm for binary optimization problems.