New Active Directory and Exchange Organization Hybrid Setup Order of Operations

Question

A brand new company (with no existing data) is creating a new on-premises Active Directory domain mydomainexample.com and they want to use Microsoft 365 services like Exchange Online, SharePoint, OneDrive, etc. Active Directory will be the Identity Provider and sync on premise identities to Azure AD with Azure AD Connect. They require an on premise Exchange server for reasons.

What is the recommended order of operations for installing this type of environment?

1. Setup the new Active Directory and users
2. Install Exchange 2016-19 management and mailbox role (I heard rumors the hybrid exchange key doesn’t work with 2019)
3. setup the 365 Tenant and populate with licenses
4. Run the Exchange hybrid deployment wizard to connect the on premises Exchange server to Exchange Online
5. Setup Azure AD Connect and sync users to cloud
6. License users in 365

Answer 1

That would work for your scenario, yes.
Be sure to validate the domain and the domain used should be internet routable.

And correct, if you want to use the free hybrid key, use Exchange 2016 :
https://techcommunity.microsoft.com/t5/exchange-team-blog/hybrid-configuration-wizard-and-licensing-of-your-on-premises/ba-p/608106