This study explores how the corporate entrepreneurship (CE) of state-owned enterprises (SOEs) evolves under varying conditions of state ownership and control, laws and norms, and competence in the market. For this purpose, we present a longitudinal case study focused on the Spanish postal operator Correos using qualitative archival data and interviews. Our results indicate that the willingness and capacity of an SOE to act entrepreneurially depends critically on its degree of autonomy from the state and on the extent to which its legal and market environments increase its dynamism, complexity, and hostility. We also show that the development of CE in an SOE may lead to improved service quality, operational efficiency, and business specialization; facilitate its market positioning; and foster its sustainability through the exploration and exploitation of strategic alliances that can increase its business scope.