The implementation of performance management has its own drawbacks. When a particular performance management technology is applied in an organization, it does not always come to fruition. Sometimes it ends as a formality, sometimes it stops at measurement phase and never reaches the management phase. This assertion is supported by a number of factual complexity problems found in East Java province, Indonesia. Using Soft Systems Methodology (SSM) (Checkland and Scholes, 1990), this research has successfully reconstructed a set of building blocks of Performance-Driven Culture, which are expected to bring improved effectiveness in the application of Performance Management. This application of SSM was conducted with a framework of dual imperative action research (McKay and Marshall, 2001) that makes it possible to do research interest reflection based on a theoretical framework; and at the same time the researchers gain a significant field research experience which is a potential basis for a problem solving action (Hardjosoekarto, 2013).Based on the theoretical framework developed by Marr (2009), this research finds that in Indonesian local government, especially in East Java province, there are five building blocks of performance-driven culture, namely: (1) leadership that encourages performance; (2) acknowledgement and appreciation of performance; (3) efficient performance reporting; (4) interactive performance review; and (5) performance map. Furthermore, together with the actors in the Government of East Java Province, this study also performed problem-solving upon the problem related to the management of elements that construct Performance-Driven Culture. The result of this problem-solving process leads to a number of agreed recommendations, namely the involvement of the Governor in Planning Forum, the initiation of performance appreciation program, the simplification of performance report framing, dialogic periodical review, establishing Performance Data Center, and the framing of integrated performance indicators.