404 on localized entries - Nginx
Seems like I needed a bit more configurations for NGINX, something like

location /es/ {
    try_files $uri $uri/ @esrewrites;
}

location @esrewrites {
    rewrite ^/es/(.*)$ /es/index.php?p=$1? last;
}


for each locale. 
Source: https://gist.github.com/cmalven/5cc95cce4e495d3a11df

Still not sure if there is a better option that avoids hard coding locales in NGINX config file.