Li7La3Zr2O12 (LLZ) solid electrolytes with Zr site partially substituted by Ta and Nb elements were prepared via the conventional solid-state reaction. All the compositions could lead to the cubic garnet-type structure after sintering at 1150 °C. The use of γ-Al2O3 as a sintering aid in the preparation of doped LLZ was studied. It was shown that Al could help to improve the micro-structure for Nb doping, but not necessary for Ta doping. The Ta and Nb doping enhanced the ionic conductivity at 25 °C to 4.09 × 10−4 S cm−1 and 4.50 × 10−4 S cm−1, respectively. A conductivity as high as 1.23 × 10−3 S cm−1 was obtained when measured at 50 °C in air for the Nb-doped LLZ. All-solid-state batteries with LLZTa and LLZNb solid electrolytes were assembled and tested. The cyclic voltammetry (CV) measurement indicated the successful working of the batteries.