Overview: Migration from local mail server or ISP-hosted email service is often a time-consuming process, therefore the ability to gradually migrate users’ email to Office 365 is a necessity; a "staged" migration. The attached PDF document explains how to run a hybrid configuration, with both the old email service and Exchange Online (Office 365) working together. Eventually the old email service can be retired.
Exchange Server 2010 and higher: Office 365 admin portal (Setup > Data migration) includes a wizard to configure hybrid (on-premise Exchange server). You may find the following article helpful to force a sync of the Azure AD objects: https://blogs.technet.microsoft.com/rmilne/2014/10/01/how-to-run-manual-dirsync-azure-active-directory-sync-updates/
(Launch "Synchronization service" to view the sync logs. Tip: ensure local AD user attribute "targetAddress" is set and pointing to SMTP:firstname.lastname@example.org - the onMicrosoft.com email address)
(Please also see attached list of Exchange Online IP addresses, which can be used to create local firewall rules)