Interesting question. Answer depends on what paste you use. Sometimes the product manual will tell you. Otherwise, just replace it when your temp starts getting too high. For myself, I've used a PC with the same thermal paste for over 2 years without replacing and it works just fine. On my laptop, I didn't change it for 2 years too. The bigger problem was always dust buildup.