1. Acesse o painel do WordPress.
2. Vá em Configurações / Links Permanentes.
3. Escolha a opção Estrutura Personalizada. Na caixa de texto apague o index.php. Clique nos botões abaixo para montar a estrutura como quiser. Sugerimos as opções %/category% e %/postname%.
Nome-do-domínio/%category%/%postname%/
A estrutura final deve ficar assim (substituindo a parte em roxo pelo seu domínio). Clique em Salvar Alterações.
4. Modifique o arquivo .htaccess do seu WordPress adicionando essas linhas:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
5. Salve as configurações e pronto, basta acessar o site novamente.