In normal circumstances, Outlook would configure itself using a procedure called Autodiscovery: all server settings and logon names would be configured by downloading configuration settings from a certain site, eliminating the requirement to know any server settings. Office 365 also makes extensive use of Autodiscovery for this and other purposes. In case of migrations, or when Autodiscovery is not available or does not apply (e.g. Outlook 2007), you can also manually configure your Office 365 account. Although this used to be pretty straight-forward, since they moved to Exchange 2013, manual configuration of Outlook has become a bit more complex.
Since its upgrade to Exchange 2013, Office 365 now uses "virtual connections points" to set up its MAPI profile (= Exchange-account). Outlook then uses "RPC over HTTP" to proxy all traffic. This is no different than Outlook Anywhere used to work, accept for the virtual connection point. Rather than providing the internal server name (like with on-premise Exchange), each user mailbox has its own unique "virtual connection point", generated from its ExchangeGUID (a unique identifier each mailbox has). In normal circumstances, when Autodiscovery is available, this information will be set up for you, but in case of manual configuration, you need to look up ExchangeGUID yourself in order to know your "virtual connection point" and set it up in Outlook.
Note that this step can only be done with an account with admin rights on your Office 365 domain.
You can retrieve a list of ExchangeGUIDs using PS. It's recommended to get them all and dump them in a CSV-file, in particular when more than one Outlook has to be configured.
Log on to Exchange Online, and compile and export the list:
Get-Recipient | Select Name,ExchangeGUID | Export-CSV -Path "my-guid-list.csv" -Force -Delimiter ";"
Adjust values for the parameters accordingly. The ExchangeGUID column contains the GUID for each mailbox. The "virtual connection point" is the Exchange server name for each mailbox, and consists of the GUID with the @your-domain appended:
E.g.: with a domain of blackmanticore.com and a GUID of 12345-67890, the server name would be firstname.lastname@example.org
Once you have the ExchangeGUID for your account and have derived the Exchange server name, you're ready to configure Outlook. Fire up Outlook and add a new Exchange-account. Be sure to select to manually add an account. If Autodiscovery has been set up, and you choose to automatically configure your account, it would continue without you being able to add the server info.
In the server name, fill in the "virtual connection point" name you got from your administrator or from the output of the PS cmdlet. The user name is simply your email address (technically, it's your UserPrincipalName). Do not click "Check Name" but click immediately on More settings to set up security and RPCoHTTP settings.
On the tab Security:
On the tab Connection, enable Outlook Anywhere (check Connect to Exchange using HTTP) and click the button to set up the HTTP proxy:
Confirm all dialogs (click OK twice), then click the button "Check name". When all settings were entered correctly, it won't give an error and will underline the server and user name. Click "Next" and "Finish" to finish the configuration.