The first search for the rare radiative decay $\Xi_b^- \to \Xi^- \gamma$ is performed using data collected by the LHCb experiment in proton-proton collisions at a center-of-mass energy of 13 TeV, corresponding to an integrated luminosity of 5.4 fb$^{-1}$. The $\Xi_b- \to \Xi^- J/\psi$ channel is used as normalization. No $\Xi_b^- \to \Xi^- \gamma$ signal is found and an upper limit of $\mathcal{B}(\Xi_b^- \to \Xi^- \gamma) < 1.3 \times 10^{-4}$ at 95% confidence level is obtained.