Developing a critical-element-free low-cost permanent magnet is an urgent necessity in view of rapidly developing technologies and the associated huge market demand for Nd2Fe14B-based magnets. Here, inspired by the abundant and low-cost nature of Ce and these high-performance Nd2Fe14B permanent magnets, we explore whether it is in fact possible to attain a useful performance in alloys based on the sister material Ce2Fe14B, employing both experimental and theoretical efforts. Experimentally, we study Ce2Fe14B with Co, La, and Zr substitutions. The Zr substitution is explored in view of Zr’s frequent role in enhancing magnetic anisotropy in permanent magnets, while the Co and La substitutions serve to remedy the too-low Curie point of 433 K in the base alloy. While we find no Zr-related anisotropy enhancement either experimentally or theoretically, the cosubstitution of La and Co indeed improves the Curie temperature as well as the magnetization, Ms, with a potential energy product as high as 38 MG Oe. These properties together suggest optimization of the alloy LaCeFe12.7Co1.3B (with only 7 wt % cobalt) as a critical-element-free permanent magnet. While the substituted elements do not enhance magnetic anisotropy, from theory, we find a substantial increase, to a first anisotropy constant, K1, as high as 4.24 MJ/m3, associated with Bi substitution for Ce. Our experimental and theoretical results demonstrate the great potential of La, Co, and Bi substitutions in developing low-cost and critical-element-free Ce2Fe14B-based permanent magnets.