In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is $$2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon $$ 2+1/p+3+2/p+1/p2+ϵ , where $$p \in {\mathbb {Z}}_+$$ p∈Z+ is a parameter of the algorithm and $$\epsilon >0$$ ϵ>0 is a positive number.