Fast and accurate crystal structure prediction (CSP) algorithms and web servers are highly desirable for the exploration and discovery of new materials out of the infinite chemical design space. However, currently, the computationally expensive first-principles calculation-based CSP algorithms are applicable to relatively small systems and are out of reach of most materials researchers. Several teams have used an element substitution approach for generating or predicting new structures, but usually in an ad hoc way. Here we develop a template-based crystal structure prediction (TCSP) algorithm and its companion web server, which makes this tool accessible to all materials researchers. Our algorithm uses elemental/chemical similarity and oxidation states to guide the selection of template structures and then rank them based on the substitution compatibility and can return multiple predictions with ranking scores in a few minutes. A benchmark study on the 98290 formulas of the Materials Project database using leave-one-out evaluation shows that our algorithm can achieve high accuracy (for 13145 target structures, TCSP predicted their structures with root-mean-square deviation < 0.1) for a large portion of the formulas. We have also used TCSP to discover new materials of the Ga-B-N system, showing its potential for high-throughput materials discovery. Our user-friendly web app TCSP can be accessed freely at www.materialsatlas.org/crystalstructure on our MaterialsAtlas.org web app platform.