Resting heart rate (rHR) and heart rate variability (HRV) are non-invasive measurements that predict the risk of sudden cardiac death (SCD). Marine n-3 polyunsaturated fatty acid (PUFA) supplementation may decrease rHR, increase HRV, and reduce the risk of SCD. To date, no studies have investigated the effect of marine n-3 PUFA on HRV in renal transplant recipients. In a randomized controlled trial, 132 renal transplant recipients were randomized to receive either three 1 g capsules of marine n-3 PUFA, each containing 460 mg/g EPA and 380 mg/g DHA, or control (olive oil) for 44 weeks. HRV was calculated in the time and frequency domains during a conventional cardiovascular reflex test (response to standing, deep breathing, and Valsalva maneuver) and during 2 min of resting in the supine position. There was no significant effect of marine n-3 PUFA supplementation on time-domain HRV compared with controls. rHR decreased 3.1 bpm (± 13.1) for patients receiving marine n-3 PUFA compared to 0.8 (± 11.0) in controls (p = 0.28). In the frequency domain HRV analyses, there was a significant change in response to standing in both high and low frequency measures, 2.9 (p = 0.04, 95% CI (1.1;8)) and 2.7 (p = 0.04, 95% CI (1.1;6.5)), respectively. In conclusion, 44 weeks of supplemental marine n-3 PUFAs in renal transplant recipients significantly improved the cardiac autonomic function, assessed by measuring HRV during conventional cardiovascular reflex tests.