As I understand it, the universe actually started in a heat-death state (very small temperature differences, homogeneous and isotropic), it's just that it is a very hot heat death state, not the usual cold one where everything freezes.

Then it is the universe expansion that made the entropy per volume decrease, actually allowing complex systems to evolve. The expansion still has to occur faster than the entropy increase rate but I read somewhere that the universe total entropy did not increase that much since the Big Bang.