The hyperoctahedral group acting on ^N is the Weyl group of type B and is associated with a two-parameter family of differential-difference operators {T_i:1 i N}. These operators are analogous to partial derivative operators. This paper finds all the polynomials h on ^N which are harmonic, _Bh = 0 and annihilated by T_i for i>2, where the Laplacian . They are given explicitly in terms of a novel basis of polynomials, defined by generating functions. The harmonic polynomials can be used to find wavefunctions for the quantum many-body spin Calogero model.