I thought that I didn't install some of components probably, but this was not the case.
I'm in the middle of migration from on-premises to the cloud.
I have not finished configuring main domain and I've tried to connect to Office365 with the main domain which MX record still points to on-premises server.
If you need to manage user accounts in Office365 and you didn't moved your domain the cloud, use the WWW panel(EAC).
After migration I still cannot use MSolService module.
I've found the right reason: the module was in System32 path folder, which is used by 32bit systems.
After moving it to the same place in SysWow64 path, module has been loaded correctly.
So, the really fix is:
Copy folders MSOnline and MSOnlineExtended from C:\Windows\System32\WindowsPowershell\v1.0\Modules