The linear complexity of sequences is an important measure to gauge the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu, Niederreiter, and Su [3] studied linear complexity and 1-error linear complexity of 2 n -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 n -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 n -periodic binary sequences with fixed 2-error or 3-error linear complexity L, when the Hamming weight of the binary representation of 2 n − L is $w_H(2^n-L) \neq 2$ . Using this characterization we obtain the counting function for the number of 2 n -periodic binary sequences with fixed k-error linear complexity L for k = 2 and 3 when $w_H(2^n-L) \neq 2$ .