Deep neural networks have achieved significant success in image dehazing. However, existing backbones face an irreconcilable trade-off between the global receptive field and computational efficiency, hindering further applications. State space models, such as Mamba, offer a potential solution to this conflict by modeling long-range dependencies with linear complexity. Although Mamba is well-suited for sequential tasks (e.g., natural language processing), it still encounters challenges when applied to low-level vision tasks. In this work, we propose a large multi-modal model (LMM) guided, Mamba-based image dehazing method (DehazeMamba). It enhances the standard Mamba architecture by incorporating image quality priors provided by the LMM and a channel attention mechanism. Additionally, we present a challenging image dehazing dataset and conduct new benchmark studies based on the LMM, evaluating hazy images and dehazing results by simulating human perception. Our experimental results demonstrate that our dataset exhibits superior haze quality, and our method outperforms current state-of-the-art (SOTA) dehazing methods by achieving a performance improvement of more than 5% on both the O-Haze and Dense-Haze datasets.