Background: Regenerex® is a porous titanium construct with a 3D interconnecting pore structure and biomechanical characteristics close to that of normal trabecular bone. This study aimed to compare the Regenerex (VR) to the non-interconnecting pore structure Porous Plasma Spray (VP) on tibial implants for total knee arthroplasty (TKA) at 5 years. Methods: We enrolled and randomized 61 patients (mean age = 63(49–71) years, Female/Male = 35/26) who were planned for an uncemented Vanguard TKA (Biomet, Warsaw, Indiana, USA) to receive either a VR or a VP coated tibial component (31/29). We performed radiostereometric analysis (RSA) and Dual Energy X-ray Absorptiometry (DEXA) postoperatively, and at three, six, 12, 24 and 60 months with measurements of migration. In total 55 patients attended the 5-year follow-up. Results: One patient died and four were reoperated during the 60-months period; none due to aseptic loosening. All reoperations were in the VR-group. The mean (range) 60-months MTPM was 1.4 mm (0.5–3.7) for the VP-group and 1.8 mm (0.4–4.9) for the VR-group (p = 0.8). The 24 to 60-months mean (range) MTPM was −0.3 mm (−5 to 1.24) in the VP-group and 0.2 mm (−0.4 to 3.5) in the VR-group (p = 0.8). Conclusion: We did not find any statistically significant differences between the VP- and VR-group and both groups show recognizable migration. We will continue to follow the groups for years to come.