Migrating from Exchange 2016 to Office 365

Hi, it depends also on how many mailboxes your organization has to manage.
Also have a look at supported migration paths, it’s useful background and will help you make up your mind.
https://support.office.com/en-us/article/decide-on-a-migration-path-0d4f2396-9cef-43b8-9bd6-306d01df1e27

Use Exchange Deployment Assistant.

https://technet.microsoft.com/en-us/office/dn756393.aspx

Just enter your scenario and it will give you the guidance you need.

Another one is Stellar EDB to PST Converter. The software helps you to migrate mailboxes from Exchange Server to Office 365.
https://www.stellarinfo.com/support/kb/index.php/article/convert-offline-edb-to-office365

Thank you all very good information, I should have mention that this is a really small environment,  there are less than 75 users.  Also, timgreen7077 not that I do not disagree with you and I am trying to only learn here.  I am curious as why would it not work, I believe I could have two MX record one with a higher priority and then one with a lower priority.  If the mailbox is not found with the higher priority would it not check the secondary mailbox?  Again, just want to learn from you and see what am I missing point of view.  Thank you again everyone.

The issue is that the MX record has nothing to do with actual mailboxes. Its the email domain that the record references, so if you have 2 MX records pointing to 2 different companies (your 3rd party hosted company and O365), if the mailbox is no longer in the 3rd party environment but it has been moved to O365, but the host 3rd party it still accepts emails for that domain, the email will just fail because recipient wont be found, it will not look at the second MX record. The 2nd MX record is used if the 1st one can't be contacted.

timgreen7077 - Thank you, so the second MX record works as a whole and not on an individual mailbox.  I see exactly what you mean now, so with your suggestion creating the new mailbox on O365 first and then changing the MX records should work just fine in that case.  But once the MX record is reported and mail is flowing to the new email server.  Is it possible for the clients to still be connected to the old mailbox for migration or just check one last time to make sure that no emails were missed.  Thank you again for the explanation.

Once you point the MX records to the new environment, you will have to wait for DNS replication. Replication can take up to 48hrs but I have never seen it take that long. It normally takes a few hours for DNS replication. Once replication is complete, all mail will start going to the new environment which will be O365. Depending on your current hosted company, all those users still should be able to access their emails or until you cut off that service. Export the emails for the users to a pst file, and then it can be imported into the new mailbox in O365. since you can't setup hybrid the export to pst will be the method to use and then import those pst files into the new mailbox you created in O365. there are also 3rd party tools that can help with getting the pst files imported for you.

Thank you all