The Atlantic Multidecadal Variability (AMV) is a large-scale climate phenomenon with crucial impacts on human societies and ecosystems. Its periodicity and drivers are controversial due to the short temporal extent of instrumental observations and competing impacts of external forcing and internal variability. Here, we use a well-verified set of paleoclimate proxy records and compare four regression methods to perform different reconstructions of the AMV since 850 C.E., built to only reflect internal variability in the Atlantic. The best performing reconstruction, when verified both against climate model outputs and independent proxy records is obtained using the non-linear random forest method. It exhibits large multi-decadal variations in the range of 20-90 years, a broader range than the 50-70 years identified in instrumental records. The reconstruction shows that AMV autocorrelation properties have experienced a significant change in the recent decades, suggesting an early warning signal for the proximity of a tipping point in the Atlantic.