The soil feels very nice after doing it but I don't know how good it would be for the plants. I want to use some fertilizer after doing it. Those little stones would still, of course, remain there a few centimeters deep down below the surface. Is it a good idea?
That soil sure does look to be a tough place to grow plants in...
To start, have you had a soil test done? If not, I strongly recommend that you do so before adding any fertilizer, because the results of the test will help you in choosing the correct fertilizer for your garden. Given that you used "centimeters" in your post, I'm assuming that you aren't in the US (where I'm located), so I'm not able to recommend where you can get the soil tests done in your country.
I would also be curious about the soil's composition (sand, silt, clay, or loam). The "jar test" can give you that information quickly and easily. [Note - this link taken from a random web search; using "soil test composition" as search terms will give you many more options, some with much better explanations of the results]
Once you have this information in hand, you can decide on whether you want to sift or not. Be aware that the pebbles lower in the soil profile will rise over time, so your sifted soil may look like it does now after only a few years. My own inclination, if I were in your garden, would be to not sift. Unless you grow root crops (especially carrots), the pebbles will not adversely affect your plants by themselves.
Whether or not you decide to sift the soil, I strongly recommend that you add compost and/or other organic matter yearly, in order to build soil tilth. This will help with water retention, drainage (slowing it down if the soil is sandy and speeding it up if the soil is clay), and general plant health. Compost is itself a mild fertilizer as well. I also recommend an organic mulch: something like pine needles, cocoa bean hulls, rice hulls, even leaf mould all are good mulches, helping the garden retain moisture and adding organic matter to the soil (and improving its tilth) as they decay (if you were creating a landscape garden, I would strongly recommend that you use arborist wood chips as your mulch). The type of mulch you can use depends upon what's available locally. You will have to add new mulch every spring, after planting (I add my mulch after the seedlings have two or three sets of leaves).
Another option would be to build bottomless raised beds and grow your vegetables in them. Because differences between soil pore sizes can negatively affect drainage, I would gently mix (just a bit) the bottom 5cm of good soil in the raised bed with the top 5cm of soil beneath it. The advice about compost and mulch still applies with raised beds.
As you can see, your question is more complex than "should I sift or not" :) You are definitely correct in being concerned about your soil, as that it is arguably the most important part of any garden. Best of luck with your new garden!