"New game plus - quests will have no rewards..."

[Seraph522]

Harder difficulties wasn't the main selling point at first until the Souls series popularized it with enemy and boss stats scaling up by a certain percentage every time you beat the game.

When NG+ first became a thing, it was more to do with just replaying the game with new features.

They definitely existed before the Souls games; I still remember Golden Sun: The Lost Age had two NG+ versions, one that carried over your levels and one that started you over with much tougher enemies. And FFXII: IZJS introduced both NG+, which started you over with all characters at level 90, and NG-, which restricts you from leveling up, creating a low-level challenge. Additionally, harder difficulty levels have often been locked behind an initial playthrough in some games; Kingdom Hearts II: Final Mix did this with Critical mode, and Fire Emblem: Radiant Dawn similarly locked Hard mode (Maniac Mode in Japanese; that game had some weird localization problems in regards to its difficulty settings) behind completing the game once.

That being said, it was almost always an option rather than the primary selling point of NG+, which is definitely the case with the Souls games, so that popularized that trend to some degree.

Edit: I can't confirm whether or not KHII: Final Mix locked Critical mode behind game completion, so take that example with a grain of salt.