We show that a recently constructed five-dimensional (5D) model with gauge-Higgs unification and explicit Lorentz symmetry breaking in the bulk, provides a natural dark matter candidate. This is the lightest Kaluza-Klein particle odd under a certain discrete Z(2) symmetry, which has been introduced to improve the naturalness of the model, and resembles KK-parity but is less constraining. The dark matter candidate is the first KK mode of a 5D gauge field and electroweak bounds force its mass above the TeV scale. Its pair annihilation rate is too small to guarantee the correct relic abundance; however coannihilations with colored particles greatly enhance the effective annihilation rate, leading to realistic relic densities.