Step 1: Login into portal.office365.com

Sign in with your Login ID and Password.

Continue…

Step 2: When entering account click on Admin as shown into the picture.

Step 3: Click on the Exchange and a new window will open.

Step 4: In new window click on the Mail Flow. 

Then click on the Message Trace

Step 5: Click on the Add Recipient section.

Step 6: After click on the Add recipient a new pop up window will appear on the screen now select one of the users and click on Ok button.

Step 7: Now click on the Search button and it will show all the messages.