The development of high-throughput ‘omic techniques has sparked a rising interest in genome-scale metabolic models, with applications ranging from disease diagnostics to crop adaptation. Efficient and accurate methods are required to analyze large metabolic networks. Flux sampling can be used to explore the feasible flux solutions in metabolic networks by generating probability distributions of steady-state reaction fluxes. Unlike other methods, flux sampling can be used without assuming a particular cellular objective. We have undertaken a rigorous comparison of several sampling algorithms and concluded that the coordinate hit-and-run with rounding (CHRR) algorithm is the most efficient based on both run-time and multiple convergence diagnostics. We demonstrate the power of CHRR by using it to study the metabolic changes that underlie photosynthetic acclimation to cold of Arabidopsis thaliana plant leaves. In combination with experimental measurements, we show how the regulated interplay between diurnal starch and organic acid accumulation defines the plant acclimation process. We confirm fumarate accumulation as a requirement for cold acclimation and further predict γ–aminobutyric acid to play a key role in metabolic signalling under cold conditions. These results demonstrate how flux sampling can be used to analyze the feasible flux solutions across changing environmental conditions, whilst eliminating the need to make assumptions which introduce observer bias.