On Nelson Mandela International Day, and with the topic of gender equality top of the agenda at the United Nations this week as countries review their progress on the Sustainable Development Goals, I couldn’t help from reflecting on Nelson Mandela’s – or Madiba, as we fondly call him in South Africa – approach toward gender equality and women.

Mandela was released in February 1990 after spending 27 painful and cruel years behind prison bars and walls, primarily in solitude or in male-only environments. He rejoined a society scarred not only by centuries of racial oppression, but also rampant sexism and a high level of violence, particularly toward women and girls. So it was interesting that as he assumed his pivotal role of President of the African National Congress (ANC), the main liberation movement, he chose to surround himself with three strong women. As a young woman who had recently returned to South Africa after a life in exile and studying abroad, it was moving and empowering to observe our lifelong hero bucking social trends and making the choice to assert women as decision-makers and his trusted confidantes.

The first was Barbara Masekela, a former Rutgers University lecturer and former head of the ANC’s Department of Arts and Culture. She was invited to be Chief of Staff in Madiba’s office in 1990 and ultimately served as Ambassador of South Africa to the United States between 2003-2007.

Dr Frene Ginwala was instrumental in setting up Madiba’s office at the ANC’s new headquarters in Johannesburg before going on to catalyze a unified women’s movement in support of the constitutional process. She subsequently became the first woman speaker of South African’s national parliament following the historic democratic elections in 1994.

The third woman was Jesse Duarte, who served as Madiba’s Special Assistant prior to the 1994 elections and is current Deputy Secretary-General of the ANC. These three women ran Madiba’s office in those early years with efficiency and laser focus. They were visibly present and in charge, always.

A few years later, in 1995, I traveled with a group of over 100 other South African women to the Fourth UN Conference on Women in Beijing. I had spent two intense years working with a committee of dedicated women leaders from across the country to mobilize women, men, civil society, the media, parliament, and the government around the Beijing conference – the first of the UN women’s conferences in which South Africa ever participated.

Our aim was to ensure that the new South Africa took its participation in the conference seriously and adopted the Beijing Platform of Action without reservation. We had made the Convention on the Elimination of all forms of Discrimination Against Women our rallying cry, insisting that we wouldn’t go to Beijing before it was ratified by the newly elected democratic parliament.

In the days before our departure for Beijing, our office sent an invitation letter to Madiba’s office inviting him to come to the airport to bid us well. In truth, we barely expected to receive a response. Our flight – a specially commissioned one by South African Airways to carry our large NGO delegation – was postponed from Friday to late on a Saturday night. Many women had flown in from different provinces in the country and had to camp out for a night and a full day at the airport. They were irate, hungry, and tired by the time Saturday afternoon arrived.

And then Madiba entered the large, cavernous departure area with a beaming smile on his face, wearing one of his trademark patterned shirts in vivid golden-brown colors. He came straight to the crowd, walked around, and shook the hand of every single woman. My colleague had her baby son, Malik, with her, who was less than a year old. He picked up the boy and told him how lucky he was to be traveling to Beijing with all these wonderful women. The delegation broke out into joyful song and dance at the realization that Madiba had actually come through for us and that he took our mission as women activists seriously and was ready to spend part of his weekend to come and ensure that we departed for Beijing with our heads held high.

Fast forward to July 1996. I was now a diplomat, freshly posted as Counsellor at the South African embassy in Paris. Barbara Masekela was now serving as South Africa’s first black and female ambassador to France and was my boss and a daily inspiration. Madiba was invited by President Jacques Chirac to pay a state visit to France. Long divorced from the fiery and powerful Winnie Mandela, during his Paris visit, Madiba confirmed his attachment to Graça Machel, former First Lady of Mozambique, apparently saying that she “made him bloom like a flower.”

We all benefited from the beauty and strength of their relationship not just then, but for the precious years until Madiba left us in December 2013. Graça Machel had been appointed Minister of Education of Mozambique at the young age of 30 and was a tireless advocate for the empowerment of women and girls. She was yet another strong female role model that Madiba chose to surround himself with.

“It’s no use for a leader to surround himself with yes-men,” was Madiba’s credo. Instead, he was a unique leader who saw brilliant, empowering women not just as his equals, but even as his role models. As we celebrate his life today on July 18, I’m grateful to take this moment to recognize the rare and confident leadership of a man who was unafraid to honor the power and intelligence of women.