A k-magic square of order n is an arrangement of the numbers from 0 to kn-1 in an n by n matrix, such that each row and each column has exactly k filled cells, each number occurs exactly once, and the sum of the entries of any row or any column is the same. A magic square is called k-diagonal if its entries all belong to k consecutive diagonals. In this paper we prove that a k-diagonal magic square exists if and only if n = k = 1 or 3 <= k <=n and n is odd or k is even.