there are a few options you have available. You could just save those .pst files. Connect all the users exchange to Office 365, import the PST files and just let Outlook upload the imported mail to Office 365.
A third option is to use something BitTitan to migrate the mail from one mailbox to another. It can connect to your existing host over POP3, connect to Office 365 and just copy the mail. This is usually my preferred approach, but it does cost a little bit, although for what you get an the time it saves, it's well worth it in my opinion - https://www.bittitan.com/migrationwiz/mailboxes/