Non-geometric string backgrounds were proposed to be related to a nonassociative deformation of the space-time geometry. In the flux formulation of double field theory (DFT), the structure of mathematically possible non-associative deformations is analyzed in detail. It is argued that on-shell there should not be any violation of associativity in the effective DFT action. For imposing either the strong or the weaker closure constraint we discuss two possible non-associative deformations of DFT featuring two different ways how on-shell associativity can still be kept.