We present the first study on the amplification of magnetic fields by the turbulent dynamo in the highly subsonic regime, with Mach numbers ranging from $10^{-3}$ to $0.4$. We find that for the lower Mach numbers the saturation efficiency of the dynamo, $(E_{mathrm{mag}}/E_{mathrm{kin}})_{mathrm{sat}}$, increases as the Mach number decreases. Even in the case when injection of energy is purely through longitudinal forcing modes, $(E_{mathrm{mag}}/E_{mathrm{kin}})_{mathrm{sat}}$ $gtrsim 10^{-2}$ at a Mach number of $10^{-3}$. We apply our results to magnetic field amplification in the early Universe and predict that a turbulent dynamo can amplify primordial magnetic fields to $gtrsim$ $10^{-16}$ Gauss on scales up to 0.1 pc and $gtrsim$ $10^{-13}$ Gauss on scales up to 100 pc. This produces fields compatible with lower limits of the intergalactic magnetic field inferred from blazar $gamma$-ray observations.