In order to engineer an open quantum system and its evolution, it is essential to identify and control the memory effects. These are formally attributed to the non-Markovianity of dynamics that manifests itself by the evolution being indivisible in time, a property which can be witnessed by a non-monotonic behavior of contractive functions or correlation measures. We show that by monitoring directly the entanglement behavior of a system in a tripartite setting it is possible to witness all invertible non-Markovian dynamics, as well as all (also non-invertible) qubit evolutions. This is achieved by using negativity, a computable measure of entanglement, which in the usual bipartite setting is not a universal non-Markovianity witness. We emphasize further the importance of multipartite states by showing that non-Markovianity cannot be faithfully witnessed by any contractive function of single qubits. We support our statements by an explicit example of eternally non-Markovian qubit dynamics, for which negativity can witness non-Markovianity at arbitrary time scales.