Acabo de transferir mi pagina web a otro Hosting y noto que los permalinks no funcionan, esto puede ser debido a que el modulo redirect no este habilitado en Apache, etc.
Pero en mi caso la solución la encontré en StackExchange.
Solo debia buscar la siguiente linea en el archivo /etc/apache2/apache2.conf.
<Directory /var/www/>
Options Indexes FollowSymLinks
AllowOverride None
Require all granted
</Directory>
Y cambiarla por.
<Directory /var/www/>
Options Indexes FollowSymLinks
AllowOverride All
Require all granted
</Directory>
Luego reiniciar Apache y listo.