New applications such as hybrid electric vehicles and power backup require rechargeable batteries that combine high energy density with high charge and discharge rate capability. Using ab initio computational modeling, we identified useful strategies to design higher rate battery electrodes and tested them on lithium nickel manganese oxide [Li(Ni(0.5)Mn(0.5))O2], a safe, inexpensive material that has been thought to have poor intrinsic rate capability. By modifying its crystal structure, we obtained unexpectedly high rate-capability, considerably better than lithium cobalt oxide (LiCoO2), the current battery electrode material of choice.