A random laser of a photonic crystal fiber (PCF) with holes filled with laser dye-doped nematic liquid crystal (NLC) is reported. When the excitation polarization was along the PCF axis, the measured laser threshold was 80 μJ/mm2 per pulse, which is much lower than the previously reported random laser of PCF filled with laser dye-doped organic solvent. This low threshold is due to the high refractive index of the NLC, which produces a greater scattering efficiency. In contrast, when the excitation polarization is perpendicular to the PCF axis, the threshold was much higher or the laser oscillation was absent. This is because of the lower refractive index of the NLC for the perpendicular polarization. The laser oscillation was absent in the isotropic phase because of a low fluorescence efficiency at high temperatures.