본관은 의령(宜寧). 초명은 남종순(南鍾順), 자는 성휴(聖休). 남영중(南英中)의 아들이다.
1848년(헌종 14) 증광별시 문과에 을과로 급제, 철종 때 동래·이천의 부사 등을 역임하였다.
1866년(고종 3) 병인박해가 시작될 무렵 우승지로서 문중(門中)의 현직관리들과 함께 천주교도의 대표격으로 지목되어 체포당한 전 승지(承旨) 남종삼(南鍾三)의 처벌을 요구하는 상소를 올렸다. 남종삼사건 이후 주위의 오해를 피하려고 1868년부터 남종순이라는 초명을 남정순으로 바꾼 듯하다.
그뒤 대사간·이조참판·호조참판·규장각직제학을 거쳐 1872년 평안도관찰사가 되었다. 평안도관찰사 재임 중 당시 성행하던 청국선(淸國船)의 밀무역을 막는 데 공헌하였으나, 사소한 행정상의 실수로 고금도(古今島)에 유배당하였다.
그뒤 각각 두 차례에 걸쳐 한성부판윤·형조판서 등을 지냈다. 또한 강원도관찰사·함경도안무사·공조판서 등을 거쳐 1894년 이조판서가 되었다. 1896년 궁내부특진관(宮內府特進官)이 되고 칙임관(勅任官) 3등에 서임되었다. 1897년에는 중추원1등의관(中樞院一等議官)이 되고 칙임관 2등에 서임되었다.
함경도안무사로 있을 때 국방력의 강화를 위하여 종래 유명무실하던 영포군(營砲軍)을 정비하였으며 길주민란을 진압하였다. 할아버지인 남이익(南履翼)과 함께 기로소(耆老所)에 들어갔다. 시호는 효정(孝貞)이다.