When you install or reinstall Windows 8 (not its 8.1 update), you will notice that you will not be able to automatically download and install updates for Windows (and other Microsoft products, if applicable) through Windows Upate.
Here's how to quickly fix this problem.

1. Windows Update produces a 80072EFE error on a clean Windows 8 installation
2. Update the Windows Update client installed on Windows 8
3. Check for updates on Windows 8
4. Display the list of updates

1. Windows Update produces a 80072EFE error on a clean Windows 8 installation

For this tutorial, we installed Windows 8 Professional (but the edition doesn't matter) in 64-bit (x64).

Specifically, this is version 6.2 (number 9200).

As you can see, Windows Update is disabled for now.

And we never installed an update on this computer.

You try to search for updates via Windows Update and the message "Checking for updates" appears.

Except, that an error will occur:

Windows could not search for new updates.
An error occured while checking for new updates for your computer.
Error(s) found: Code 80072EFE - Windows Update encountered an unknown error.

2. Update the Windows Update client installed on Windows 8

In fact, if the Windows Update client produces this "80072EFE" error, it's because it cannot connect to the Microsoft update server.
This can happen if your computer doesn't have access to the Internet, or if a program (such as an anti-virus or anti-malware) is preventing Windows Update from connecting to the Internet.

However, if you have just installed Windows 8, the real problem is simply that the Windows Update client installed by default on Windows 8 is not up to date and therefore it can no longer connect to the update server of Microsoft.
Fortunately, Microsoft offers an "Update the Windows Update Agent to the latest version" page where the download links are referenced to easily get the latest version of Windows Update client for Windows 7 SP 1 and 8 (as well as corresponding server editions).
Once the Windows Update client is updated, your computer will be able to automatically check for and download all necessary updates through Windows Update.

On this "Update the Windows Update Agent to the latest version" page, you will find a "Stand-alone packages for Windows 8 and Windows Server 2012" section with 2 download links for Windows 8.
Choose the download link appropriate for your Windows architecture :

• 32-bit (x86) : All supported x86-based versions of Windows 8 (KB2937636)
• 64-bit (x64) : All supported x64-based versions of Windows 8 (KB2937636)

Info : if these download links no longer work, search this KB2937636 update on the Microsoft Update Catalog.

As explained at the start of this tutorial, we installed a 64-bit (x64) version of Windows 8.
So, we are downloading the x64 version of this "KB2937636" update.

By default, the page is displayed in English, but you can select an another language from the list to translate the page automatically.
Then, click on the "Download" button.

The file that will be downloaded is :

• Windows8-RT-KB2937636-x64.msu (if you have chosen the 64-bit version)
• Windows8-RT-KB2937636-x86.msu (if you have chosen the 32-bit version)

To install this update, double click on the downloaded "Windows8-RT-KB2937636-x...msu" file.
A "Windows Update Standalone Installer" window will appear.

Wait while the update is installed.

After the update is installed, you will need to restart your computer.

During the restart, the "Configuring Windows Updates - xx% Complete" message will appear.

Then, go back to Windows Update.