The small dimensions of optical fiber sensors are of particular interest to biological applications, given the ability to penetrate relatively inaccessible regions. However, conventional optical fibers are larger than biological material such as cells, and thus there is a need to further miniaturize fiber sensors. Here we present the fabrication of ultra-small Fabry-Perot cavities written into optical micro-fibers using focused ion beam milling. We have fabricated cavities as small as 2.8 µm and demonstrated their use for sensing of both bulk refractive index and thin-layer coatings. In order to achieve sensitive measurements we interrogate at visible wavelengths, thereby reducing the free spectral range of the interferometer (relative to infra-red interrogation), increasing the number of interference fringes, and allowing for the implementation of the Fourier shift method.