Graph neural networks (GNNs) have demonstrated success at learning representations of brain graphs derived from functional magnetic resonance imaging (fMRI) data. The majority of existing GNN methods, however, assume brain graphs are static over time and the graph adjacency matrix is known prior to model training. These assumptions are at odds with neuroscientific evidence that brain graphs are time-varying with a connectivity structure that depends on the choice of functional connectivity measure. Noisy brain graphs that do not truly represent the underling fMRI data can have a detrimental impact on the performance of GNNs. As a solution, we propose DynDepNet, a novel method for learning the optimal time-varying dependency structure of fMRI data induced by a downstream prediction task. Experiments on real-world resting-state as well as task fMRI datasets for the task of biological sex classification demonstrate that DynDepNet achieves state-of-the-art results outperforming the best baseline in terms of accuracy by approximately 8 and 6 percentage points, respectively. Moreover, analysis of the learnt dynamic graphs highlights prediction-related brain regions which align with existing neuroscience literature.