Finite automata that traverse graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of Boolean operations for this model. It is proved that the union of GWA with m and n states, with (Formula presented), operating on graphs with k labels of edge end-points, is representable by a GWA with (Formula presented) states, and at least (Formula presented) states are necessary in the worst case. For the intersection, the upper bound is (Formula presented) and the lower bound is (Formula presented). The upper bound for the complementation is (Formula presented), and the lower bound is (Formula presented).