Abstract Background Sulfur is a major component of biological molecules and thus an essential element for plants. Deficiency of sulfate, the main source of sulfur in soils, negatively influences plant growth and crop yield. The effect of sulfate deficiency on plants has been well characterized at the physiological, transcriptomic and metabolomic levels in Arabidopsis thaliana and a limited number of crop plants. However, we still lack a thorough understanding of the molecular mechanisms and regulatory networks underlying sulfate deficiency in most plants. In this work we analyzed the impact of sulfate starvation on the transcriptome of tomato plants to identify regulatory networks and key transcriptional regulators at a temporal and organ scale. Results Sulfate starvation reduces the growth of roots and leaves which is accompanied by major changes in the organ transcriptome, with the response being temporally earlier in roots than leaves. Comparative analysis showed that a major part of the Arabidopsis and tomato transcriptomic response to sulfate starvation is conserved between these plants and allowed for the identification of processes specifically regulated in tomato at the transcript level, including the control of internal phosphate levels. Integrative gene network analysis uncovered key transcription factors controlling the temporal expression of genes involved in sulfate assimilation, as well as cell cycle, cell division and photosynthesis during sulfate starvation in tomato roots and leaves. Interestingly, one of these transcription factors presents a high identity with SULFUR LIMITATION1, a central component of the sulfate starvation response in Arabidopsis. Conclusions Together, our results provide the first comprehensive catalog of sulfate-responsive genes in tomato, as well as novel regulatory targets for future functional analyses in tomato and other crops.