Holographic recording with orthogonally polarized beams in a cesium-doped KNSBN [(K0.5Na0.5)0.2(Sr0.75Ba0.25)0.9Nb2O6] crystal has been studied. It was found that this kind of photorefractive crystal possesses high linear dichroism, which makes it suitable for use in polarization holography. The diffraction efficiency as a function of the polarization orientation of the reference beam and as a function of the fringe modulation at the optimum polarization orientation of the reference beam is experimentally investigated. Theoretical fitting based on Kahmann models was performed and agrees well with the experimental data. In the experiments, both polarization holography and conventional holography are used to record a binary object. The reconstruction shows that polarization holography with Ce:KNSBN is highly effective, exhibiting high diffraction efficiency and reduced fanning noise.