Comment by WorldMaker

Installing Internet Explorer 4 on Windows 95 opened up the first version of Windows Update, when it started as a web app with some custom ActiveX plugins. Windows 98 was the first time Windows Update had a bundled link in the OS, and shortly after Windows 98 introduced a "Critical Update" notification that would prompt users to open Windows Update.

Automatic updates arrived in Windows ME.

It's interesting the timeframes on Windows are often earlier than you think they are. Admittedly, a lot of users skipped Windows ME and its strange reputation, so Windows XP may have been their first time seeing automatic updates.