Commercially pure titanium (cp-Ti) is regarded as the state-of-the-art material for bone-anchored dental devices, whereas the mechanically stronger alloy (Ti–6Al–4V), made of titanium, aluminum (Al) and vanadium (V), is regarded as the material of choice for high-load applications. There is a call for the development of new alloys, not only to eliminate the potential toxic effect of Al and V but also to meet the challenges imposed on dental and maxillofacial reconstructive devices, for example. The present work evaluates a novel, dual-stage, acid-etched, Ti–Ta–Nb–Zr alloy implant, consisting of elements that create low toxicity, with the potential to promote osseointegration in vivo. The alloy implants (denoted Ti–Ta–Nb–Zr) were evaluated after 7 days and 28 days in a rat tibia model, with reference to commercially pure titanium grade 4 (denoted Ti). Analyses were performed with respect to removal torque, histomorphometry and gene expression. The Ti–Ta–Nb–Zr showed a significant increase in implant stability over time in contrast to the Ti. Further, the histological and gene expression analyses suggested faster healing around the Ti–Ta–Nb–Zr, as judged by the enhanced remodeling, and mineralization, of the early-formed woven bone and the multiple positive correlations between genes denoting inflammation, bone formation and remodeling. Based on the present experiments, it is concluded that the Ti–Ta–Nb–Zr alloy becomes osseointegrated to at least a similar degree to that of pure titanium implants. This alloy is therefore emerging as a novel implant material for clinical evaluation.