We identify a set of dynamical maps of open quantum system, and refer to them as $ epsilon $-Markovian maps. It is constituted of maps which, in a higher dimensional system-environment Hilbert space, possibly violate Born approximation but only a little. We characterize the $epsilon$-nonmarkovianity of a general dynamical map by the minimum distance of that map from the set of $epsilon$-Markovian maps. We analytically derive an inequality which gives a bound on the $ epsilon$-nonmarkovianity of the dynamical map, in terms of an entanglement-like resource generated between the system and its immediate environment. In the special case of a vanishing $epsilon$, this inequality gives a relation between the $epsilon$-nonmarkovianity of the reduced dynamical map on the system and the entanglement generated between the system and its immediate environment. We numerically investigate the behavior of the similar distant based measures of non-Markovianity for classes of amplitude damping and phase damping channels.