Procedural content generation (PCG) has been an effective strategy to quickly meet the demands of users waiting for new game boards, characters, objects, environment, narrative, etc. One feature of relevance in automated generators is the credibility of the generated content - that it produces content susceptible of being confused with human-created content. In this study, we propose an offline PCG method for generating credible initial Sokoban states, that are also entertaining for players. For this, we propose a hybrid PCG approach, combining an ad-hoc heuristic for generating base Sokoban boards with an evolutionary algorithm for positioning elements on it. We then evaluate the boards created through a user study. Results demonstrate that the proposed hybrid PCG approach is capable of generating content that is indistinguishable from human-made game boards while also being entertaining to play. The implemented PCG approach is an example of the use of evolutionary algorithms in the search for new content. Its controllability via the objective function and constraints of the optimization model, makes it suitable for generating content that meets the requirements of game designers.