When using Office 365, and if the AutoDiscover DNS records are setup correctly and working, configuring Outlook is easy. Enter the name, email address and password of the user and Outlook is able to work out all the other settings.
But, when those AutoDiscover records are not working -- either they have not been set up with or they are not functioning correctly, and either way the first thing you should try is to get those working -- you need to configure Outlook manually to connect to the Office 365 server.
To do this: On the Outlook configure screen check off the 'Manually configure server settings or additional server types' option, then Next:
Then select 'Microsoft Exchange or compatible service' and then Next:
On the next screen click on the 'More Settings' button:
Then, under the Security tab change the 'Logon network security' to 'Anonymous' :
Then on the go to the Connection tab. Check the last check box and then click on the 'Exchange Proxy Settings' button:
On the next screen enter the details exactly as shown here, then click OK:
This then takes you back to the setup screen where you will need to enter the Server as 'outlook.office365.com' and the user's full email address under 'User Name'. Then hit 'Check Name':
At this point you should get a login box. Enter the user's full email address and password and check 'Remember';
Once you click 'OK' you should see something similar to this:
You're done. Click Next and then Finish and you should now be able to open Outlook as the user.
The above screen shots are taken from Outlook 2010 but they are the same for Outlook 2013.
Sometimes, Outlook may ask for the password but that is normal behavior. I have found it useful to let the end user know a little bit about what you have done to get Outlook connected and that Outlook, occasionally asking for their password is expected and normal. I tend to think that if Outlook is asking for a password more than once a week, then resetting the Outlook mail profile is the way forward (using the above method).