Nigeria-South Africa relations are arguably the most critical bilateral ties in Africa. Yet the relationship has experienced considerable fluctuations over time, significantly influencing the trajectory of peace, sustainable development, and regional integration on the continent. The prominent roles both states occupy in Africa—and their remarkable influence—stem not only from tangible assets such as economic and military capabilities (hard power), but also from intangible assets like cultural influence, guiding principles, and diplomatic approaches (soft power). Tracing these ties from the apartheid era to the post-apartheid period in South Africa, and since Nigeria’s independence, this chapter underscores the lost decades of relations (1960–1999), marked by confrontation and tension during apartheid and under military regimes in both countries. It then highlights the golden era of relations, as well as the more recent downturn in ties. This chapter therefore adopts Afrocentrism as an analytical lens to assess the dynamics of their bilateral relations and considers how these interactions shape their regional influence and contribute to broader efforts towards integration across Africa.