With concrete’s key role in construction and infrastructure, the reduction of its carbon footprint is critical for addressing global carbon emissions. One strategy to reduce environmental impact from concrete production is to replace cement clinker or fine aggregates in concrete with industrial wastes. Mine tailings, being a high-volume under-utilized resource, possess properties making it suitable for use as a partial substitute for cement or fine aggregates. This review article provides an overview of the recent findings within the topic of tailings-based concrete (TBC). Many of the identified publications aimed to describe the mechanical performance of TBC, and to optimize the concrete mix with respect to the strength and durability. The recommended cement replacement ranged from 5 to 25% and the recommended fine aggregate replacement ranged from 20 to 60%. In general, the compressive strength was decreased with increasing use of tailings as a replacement of cement. For the use of tailings as replacement for fine aggregates, the correlation was more complex, normally the mechanical performance enhanced at low replacement levels, until it reached an optimum after which it decreased. CO2 savings for replacing fine aggregate with tailings were up to 12% and for the cement replacement up to 30%. When assessing the environmental performance, most of the publications did not account for the loss of its mechanical performance, which could lead to the risk of underestimating the environmental impact. This review not only provides a basis for understanding the mechanical, toxicological, and environmental performances of TBCs, but also links the perspectives together, unveiling the connections between them. Moreover, this review presents an organized overview of the topic of TBC and points out topics for future research.