We demonstrate the existence of spatial soliton solutions in photonic crystal fibers (PCF's). These guided localized nonlinear waves appear as a result of the balance between the linear and nonlinear diffraction properties of the inhomogeneous photonic crystal cladding. The spatial soliton is realized self-consistently as the fundamental mode of the effective fiber defined simultaneously by the PCF linear and the self-induced nonlinear refractive indices. It is also shown that the photonic crystal cladding is able to stabilize these solutions, which would be unstable otherwise if the medium was entirely homogeneous.