High entropy materials promise to overcome the instability and the degradation caused by large electrode volume variations during (de-)lithiation, i.e. during (de-)charging of a lithium battery. Nano-level heterogeneity within such materials may, however, affect the overall performance. Here, as proof-of-concept, low (GeTe, Sb2Te3) and medium ((SnSbBi)Te, (SnSbBiGe)Te) entropy tellurides, as well as medium entropy composite tellurides ((SnSbBi)Te-ZnTe), (SnSbBiGe)Te-Cu1.75Te)) have been explored for effects of entropy and heterogeneity on cycling stability and rate capability. The rate capability is shown to depend on nano-level heterogeneity rather than entropy, but the latter to be important for stable cycling; the medium entropy composite (SnSbBiGe)Te-Cu1.75Te renders up to 140 cycles with good capacity retention (87%) and agreeable average coulombic efficiency (98.8 ± 0.4%). Altogether, characterizing and controlling nano-level heterogeneity is crucially needed to improve performance and to optimize entropy-designed alloy electrodes.