There is now a new Message Trace feature in Office 365 which has been completely redesigned by Microsoft and now sits within the Security & Compliance Centre.
The new place for Message Trace is a lot easier to use and is more modern in the way it looks. There are also a few new features available which means you can find the messages you need in a much quicker and easier way:
The old message trace is still available in the Exchange Admin Centre though if you prefer!
You can view the full article that Microsoft have published regarding the new Message Trace here.