All you need is:
apt-get install php7.0-intl
No need to change php.ini or do anything else. (Tested on PHP 7 on Ubuntu 16.04).
The most up-voted answer here has you uncommenting a .dll which will never solve anything unless you are on a Windows server!