The second law of classical thermodynamics, based on the positivity of the entropy production, only holds for deterministic processes. Therefore the Second Law in stochastic quantum thermodynamics may not hold. By making a fundamental connection between thermodynamics and information theory we will introduce a new way of defining the Second Law which holds for both deterministic classical and stochastic quantum thermodynamics. Our work incorporates information well into the Second Law and also provides a thermodynamic operational meaning for negative and positive entropy production.