Wordpress - Changing permalinks gives me 404 errors on nginx

I'm using wordpress multisite with custom permalink setting: /%category%/%postname%/

/etc/nginx/site-available/domain.conf

On server{

location / {
    try_files $uri $uri/ /index.php?q=$uri$args;
}

If your root wordpress is not the webroot but http://domain.com/wordpress/:

location /wordpress/ {
    try_files $uri $uri/ /wordpress/index.php?q=$uri$args;
}

If you are using old wordpress with blogs.dir, add: location ^~ /blogs.dir { internal; alias /var/www/wordpress/wp-content/blogs.dir; access_log off; log_not_found off; expires max; }

Check the nginx configuration: sudo nginx -t

Reload nginx: sudo service nginx reload

Also try change permalink settings.

Those are Apache .htaccess rewrite rules, but you have stated that you are on an Nginx server. Nginx does not use an .htaccess-like directory level file, much less does it use the .htaccess file itself.. You need to edit the server configuration itself. The Codex has a detail sample:

# WordPress single blog rules.
# Designed to be included in any server {} block.

# This order might seem weird - this is attempted to match last if rules below fail.
# http://wiki.nginx.org/HttpCoreModule
location / {
    try_files $uri $uri/ /index.php?$args;
}

# Add trailing slash to */wp-admin requests.
rewrite /wp-admin$ $scheme://$host$uri/ permanent;

# Directives to send expires headers and turn off 404 error logging.
location ~* ^.+\.(ogg|ogv|svg|svgz|eot|otf|woff|mp4|ttf|rss|atom|jpg|jpeg|gif|png|ico|zip|tgz|gz|rar|bz2|doc|xls|exe|ppt|tar|mid|midi|wav|bmp|rtf)$ {
       access_log off; log_not_found off; expires max;
}

# Uncomment one of the lines below for the appropriate caching plugin (if used).
#include global/wordpress-wp-super-cache.conf;
#include global/wordpress-w3-total-cache.conf;

# Pass all .php files onto a php-fpm/php-fcgi server.
location ~ [^/]\.php(/|$) {
    fastcgi_split_path_info ^(.+?\.php)(/.*)$;
    if (!-f $document_root$fastcgi_script_name) {
        return 404;
    }
    # This is a robust solution for path info security issue and works with "cgi.fix_pathinfo = 1" in /etc/php.ini (default)

    include fastcgi.conf;
    fastcgi_index index.php;
#   fastcgi_intercept_errors on;
    fastcgi_pass php;
}

Had to add this piece of code to both the /sites-available/your-settings-file and /sites-enabled/your-settings-file:

server {
[...]

if (!-e $request_filename) {
    rewrite ^.*$ /index.php last;
}

[...]
}

It's working for me now.