Cannot connect to Office 365 with Outlook 2013 SP1 Error 8004010F error with Context 501 or "The version of outlook is too old" (4305746)

When trying to connect using Outlook 2013 SP1 you may see the error 8004010F error with Context 501 or "The version of outlook is too old"

Once you have Outlook 2013 SP1 installed you will need to install the June 2018 update

https://www.microsoft.com/en-us/download/details.aspx?id=57052

The version should now be: Microsoft Outlook 2013 (15.0.5041.101) MSO (15.0.4569.1506)

Once this is installed you should now be able to connect to Office 365