Network analysis provides a powerful framework for the interpretation of genome-wide data. While static network approaches have proved fruitful, there is increasing interest in the insights gained from the analysis of cellular networks under different conditions. In this work, we study the effect of stress on cellular networks in fission yeast. Stress elicits a sophisticated and large scale cellular response, involving a shift of resources from cell growth and metabolism towards protection and maintenance. Previous work has suggested that these changes can be appreciated at the network level. In this paper, we study two types of cellular networks: gene co-regulation networks and weighted protein interaction networks. We show that in response to oxidative stress, the co-regulation networks re-organize towards a more modularised structure: while sets of genes become more tightly co-regulated, co-regulation between these modules is decreased. This shift translates into longer average shortest path length, increased transitivity, and decreased modular overlap in these networks. We also find a similar change in structure in the weighted protein interaction network in response to both oxidative stress and nitrogen starvation, confirming and extending previous findings. These changes in network structure could represent an increase in network robustness and/or the emergence of more specialised functional modules. Additionally, we find stress induces tighter co-regulation of non-coding RNAs, decreased functional importance of splicing factors, as well as changes in the centrality of genes involved in chromatin organization, cytoskeleton organization, cell division, and protein turnover.