We demonstrate for what is believed to be the first time a Brillouin laser based on a holey fiber (HF). Using a simple Fabry-Perot resonator scheme containing a 73.5-m-long highly nonlinear HF with an effective area of 2.85 microm(2) , we obtain a threshold of 125 mW and a slope efficiency of ~70% . Stimulated and spontaneous Brillouin scattering effects are investigated in the HF, and we show that the high lasing threshold is due mainly to reduction of the effective gain coefficient caused by structural nonuniformity along the fiber length.