The limitation on obtaining precise outcomes of measurements performed on two non-commuting observables of a particle as set by the uncertainty principle in its entropic form, can be reduced in the presence of quantum memory. We derive a new entropic uncertainty relation based on fine- graining, which leads to an ultimate limit on the precision achievable in measurements performed on two incompatible observables in the presence of quantum memory. We show that our derived uncertainty relation tightens the lower bound set by entropic uncertainty for members of the class of two-qubit states with maximally mixed marginals, while accounting for the recent experimental results using maximally entangled pure states and mixed Bell-diagonal states. An implication of our uncertainty relation on the security of quantum key generation protocols is pointed out.