Aluminum has been long considered as promising anode material for Li ion batteries because of its low cost, abundance, and low toxicity. Aluminum undergoes alloying with lithium through intermetallic LiAl formation, which offers a relatively high theoretical capacity of 993 mAh/g compared to 372 mAh/g for graphite. However, aluminum anodes typically suffer from rapid capacity fading and failure within first few cycles due to a pronounced volume increase that accompanies the formation of LiAl alloy, which results in accumulation of mechanical stresses, pulverization and permanent loss of the active material. In this work we investigate this process in detail and propose a new approach to overcome the negative effects of the volume change. Specifically, we show that cycling Al anode coated with poly(ethylene oxide) based polymer electrolyte gives rise to formation of a stable three-dimensional porous nanostructure with the newly formed LiAl phase growing inside the polymer electrolyte. As a result, the volume changes are confined to the nanostructure/polymer layer and do not change the overall dimensions of the aluminum anode, thus allowing us to avoid pulverization of the active material and achieve stable and reversible cycling of the Al anodes. However, the amount of the active nanostructure that can be grown on planar Al substrates is limited by the resistance of the polymer electrolyte and its ability to incorporate the growing LiAl phase.