In order to find efficient solutions to real complex world problems, computer sciences and especially heuristic algorithms are often used. Heuristic algorithms can give optimal solutions for large scale optimization problems in an acceptable period. Social Spider Algorithm (SSA), which is a heuristic algorithm created on spider behaviors are studied. The original study of this algorithm was proposed to solve continuous problems. In this paper, the binary version of the Social Spider Algorithm called Binary Social Spider Algorithm (BinSSA) is proposed for binary optimization problems. BinSSA is obtained from SSA, by transforming constant search space to binary search space with four transfer functions. Thus, BinSSA variations are created as BinSSA1, BinSSA2, BinSSA3, and BinSSA4. The study steps of the original SSA are re-updated for BinSSA. A random walking schema in SSA is replaced by a candidate solution schema in BinSSA. Two new methods (similarity measure and logic gate) are used in candidate solution production schema for increasing the exploration and exploitation capacity of BinSSA. The performance of both techniques on BinSSA is examined. BinSSA is named as BinSSA(Sim&Logic). Local search and global search performance of BinSSA is increased by these two methods. Three different studies are performed with BinSSA. In the first study, the performance of BinSSA is tested on the classic eighteen unimodal and multimodal benchmark functions. Thus, the best variation of BinSSA and BinSSA(Sim&Logic) is determined as BinSSA4(Sim&Logic). BinSSA4(Sim&Logic) has been compared with other heuristic algorithms on CEC2005 and CEC2015 functions. In the second study, the uncapacitated facility location problems (UFLPs) are solved with BinSSA(Sim&Logic). UFL problems are one of the pure binary optimization problems. BinSSA is tested on low-scaled, middle-scaled, and large-scaled fifteen UFLP samples and obtained results are compared with eighteen state-of-art algorithms. In the third study, we solved UFL problems on a different dataset named M* with BinSSA(Sim&Logic). The results of BinSSA(Sim&Logic) are compared with the Local Search (LS), Tabu Search (TS), and Improved Scatter Search (ISS) algorithms. Obtained results have shown that BinSSA offers quality and stable solutions.