This Letter presents an ultrahigh resolution optic fiber strain sensor. A random distributed feedback fiber laser (RDFL) is locked by the proposed frequency-shift Pound-Drever-Hall technique, which tracks the resonant frequency change of a π-phase-shifted fiber Bragg grating. The random distributed feedback for the RDFL gives a Lorentzian envelope over the original laser frequency noise, which can suppress the thermally induced frequency noise. The frequency noise of the laser is reduced from about 100 to 20 Hz/√Hz at 1 kHz. An ultrahigh dynamic strain resolution of 140 fε/√Hz at 1 kHz is achieved.