  We present a formalism for detection of non-Markovianity through uncertainty
relations. We show that when there is an information back-flow to the system
from its environment through CP-divisibility breaking, the Choi-states
corresponding to the reduced system evolution contain at least one negative
eigenvalue. The consequent break down of uncertainty relations for such states
can be used to witness non-Markovian dynamics. We present some relevant
examples of the phenomenon for qubit channels. We further prove that square of
the variance of a suitable hermitian operator can act as a non-linear witness
of non-Markovianity. We finally show that non-Markovianity is necessary in
order to decrease the uncertainty of the states undergoing unital dynamics for
qubits. This provides another method of certifying non-Markovianity.
