Changing permalinks causes 404

Hi!

I’m trying to change permalink structure from bla/bla/?p=123 and to bla/bal/sample-post

However; whenever I do this (or any other permalink change, besides default) I’m getting a 404 on every page. All the URL’s are being updated correctly, so when I click a link it will send me to the correct link for that given URL-pattern, but the server can’t locate any files at the given location.

Does anyone have any experience with this?