The design of a complex embedded system is dominated by the definition of an optimal architecture in relation to certain performance indexes. This activity, known as design space exploration (DSE), is a great challenge for the EDA (electronic design automation) community. The enormous size of the design space, in fact, together with the long simulation time required to evaluate each system configuration during the exploration process, cause DSE to become a bottleneck in the design flow. In this paper we propose a multiobjective design space exploration methodology based on a genetic fuzzy system, the aim of which is to drastically reduce the exploration time while guaranteeing a high level of accuracy. The methodology uses a genetic algorithm (GA) for heuristic exploration and a fuzzy system to evaluate the configurations visited. Although of general application, the methodology is applied to a real case study: optimization of the performance and power consumption of an embedded architecture based on a very long instruction word (VLIW) microprocessor in a mobile multimedia application domain. The results obtained are compared, in terms of both accuracy and efficiency, with the state of the art in multiobjective DSE strategies, represented by the classical GA approach, demonstrating the scalability and effectiveness of the proposed approach.