We report on a simple and fast route to prepare lithium selenide (Li2Se) nanoparticles and show a versatile solution-based method to form uniform nanostructured carbon (C)-Li2Se composites with and without additional carbon shell. We systematically compare electrochemical performance characteristics of 50–100nm high purity Li2Se nanoparticles with that of the C-Li2Se nanocomposites for rechargeable Li battery applications. While Li2Se nanopowder show high initial capacity, it suffers from active material loss and shuttle of dissolved polyselenides, resulting in low cycling stability and resistance growth, additionally aggravated by mechanical cathode degradation induced by repetitive volume changes during cycling. By embedding Li2Se nanoparticles into a conductive carbon matrix, mechanical stability of electrodes was greatly enhanced. More importantly, the dissolution and shuttle of polyselenides was suppressed significantly even for smaller (~20nm) and thus more reactive Li2Se nanoparticles. As a result, C-Li2Se nanocomposite cathodes showed high rate capability and promising cycling stability with carbon-shell protected C-Li2Se showing virtually no degradation in 100 cycles. When compared with somewhat similar lithium sulfide (Li2S) nanoparticles and C-Li2S electrodes, we observe lower over-potential at different C-rates in case of Li2Se and C-Li2Se materials, which is advantageous for battery applications. Based on the postmortem analysis, significant Li dendrite growth observed in Li2Se/Li cells did not take place in C-Li2Se/Li and C-Li2Se@C/Li cells, suggesting that polyselenide shuttle may affect Li plating morphology. Beyond the organic electrolyte-based Li-Se batteries, all-solid Li-Se batteries based on the produced C-Li2Se nanocomposite cathode were built for the first time using conventional Li2S-P2S5 solid state electrolyte. These solid state cells showed very promising cycling stability, a single flat plateau and very small voltage hysteresis in the range of 0.1–0.4V when tested at 60 and 80°C.