The human brain is frequently modeled as a functional connectivity (FC) network to understand brain function. Graph transformer-based methods have been studied on resting-state functional magnetic resonance imaging (rs-fMRI) brain network data and have been shown to bring extensive performance improvements. However, these methods suffer from the bottleneck of high computational cost. Recently, State Space Models (SSMs), such as Mamba, have emerged as powerful tools for modeling long-range dependencies in sequential data, owing to their effectiveness and efficiency. Nevertheless, adapting SSMs to non-sequential graph data presents a considerable challenge. In this paper, we propose a novel graph neural network, Brain Network Mamba (BNMamba), that integrates a state space model for brain network analysis. Specifically, a graph tokenization block is designed to transform graph-structured brain networks into sequential representations through a node prioritization and permutation strategy. Subsequently, we introduce a bi-directional Mamba block that captures long-range dependencies and enhances permutation robustness by scanning the node sequence in different directions. Comprehensive experiments on two publicly accessible datasets, Autism Brain Imaging Data Exchange(ABIDE) and REST-meta-MDD, demonstrate that BNMamba outperforms state-of-the-art (SOTA) methods while achieving lower computational requirements in both FLOPs and GPU memory consumption.Codes are available at https://github.com/z-GitHub-l/BrainNetworkMamba .