Puchenstuben wurde erstmals im Jahre 1261 erwähnt, allerdings handelte es sich dabei um den Ort Gösing, der zur Gemeinde Puchenstuben gehört. Wörtlich war in der Urkunde des Stiftes Lilienfeld die Siedlung Göznich erwähnt. „Göznich“ ist ein slawisches Wort, dass übersetzt so viel wie „Geißenberg“ bedeutet.
Auch das Trefflingtal war schon im Mittelalter besiedelt und trug den Namen Sulzbichl. Wegen des Wasserreichtums des Trefflingbaches gab es auch viele Mühlen, darunter auch die Trefflingmühle, die wahrscheinlich 1449 erbaut wurde und von der auch heute noch Reste vorhanden sind.
Der Ortsname stammt wahrscheinlich von einer aus Buchenholz gemachten „Stube“, entlang des einstigen Wallfahrerwegs nach Mariazell. Aus „Buchen“ und „Stube“ entstand zuerst „Buchenstuben“ und später der Ortsname „Puchenstuben“.