Exchange Onlineへのメールの移行は可能ですか？

はい、以下のケースでのメールの移行が可能です。

• メールサーバーからの移行（IMAP形式）
  Exchange OnlineにIMAP専用の移行機能があり、こちらを設定していただくことで移行が可能です。
  IMAP専用の移行機能でGmailからの移行も可能です。
  http://technet.microsoft.com/ja-JP/library/jj874018(v=exchg.150).aspx
• メールクライアントからの移行（POP/SMTP形式でOutlookを利用の場合）
  Outlookをお使いの場合、メールのファイル（PSTファイル）を使っていただくことで、Outlook 2013へインポート、 もしくは現在お使いOutlookのメールサーバーの接続先をOffice 365に変更していただくことでメールの移行が可能です。