This problem occurs if mod_rewrite function is not probably working on the server, in this case you’ll need to contact the host provider to enable this function or you can simply overwhelm this issue by manually editing the .htaccess file. It should look like this:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
If it doesn’t contain what is written above then definitely this was the problem, so just add it, save the file and refresh your page (it should work).
If the problem exists then you should consider installing a fresh copy of WordPress.