For a fiber to guide light, even considering the situation using only geometrical optics, there must be total internal reflection (TIR) at the boundary of the fiber core. For TIR to occur, the angle of incidence of the light must be greater than the critical angle $\theta_c$. If the material before the boundary has index of refraction $n_1$ and the material after the boundary has index $n_2$, then the critical angle is:
$$ \theta_c = \arcsin(\frac{n_2}{n_1})$$
Of course, if $\frac{n_2}{n_1} > 1$ then the critical angle is undefined -- TIR cannot occur. This is why TIR is only possible when light encounters an interface with a material of lower index. This should be familiar to you if you think about it: you can see the bottom of a pool from above the water, but the water surface looks silvery and reflective from underneath; the reflective face of a roof prism looks reflective when you try to look through it from the glass-to-air side, but if you look from the air side, you can see clearly.
On its own, this doesn't require a fiber to have cladding. Air has an index very near 1, so any other material will have a higher index, and therefore guide light without a cladding. However, this situation would be very unstable. Any material contacting the fiber could produce an area where TIR does not occur, and suddenly the fiber would begin leaking. Consider how easy it would be for this to happen! Any sort of dirt or oil on the fiber would either eliminate TIR completely, or raise the critical angle such that some of the light could escape. The same would be true of most materials you might use to mount the fiber, or even any type of coating you might apply as a mechanical barrier to dirt.
Thus, in practice, fibers have a cladding to ensure that the optical guiding characteristics continue to work in real world conditions. They also provide engineers with another way of adjusting the properties of the fiber, so its definitely not something we are unhappy about.
Do keep in mind though, that there are examples of unclad "fibers" although they are usually just acrylic rods used in teaching demonstrations, so I wouldn't really call them a fiber in the common sense of the word.