We prove that the quantum relative entropy decreases monotonically under the application of any positive trace-preserving linear map, for underlying separable Hilbert spaces. This answers in the affirmative a natural question that has been open for a long time, as monotonicity had previously only been shown to hold under additional assumptions, such as complete positivity or Schwarz-positivity of the adjoint map. The first step in our proof is to show monotonicity of the sandwiched Renyi divergences under positive trace-preserving maps, extending a proof of the data processing inequality by Beigi (J Math Phys 54:122202, 2013 ) that is based on complex interpolation techniques. Our result calls into question several measures of non-Markovianity that have been proposed, as these would assess all positive trace-preserving time evolutions as Markovian.