본관은 의령(宜寧). 자는 훈중(熏中), 호는 파은(坡隱). 할아버지는 사도시정 남두첨(南斗瞻)이고, 아버지는 관찰사 남훤(南翧)이며, 어머니는 권현(權俔)의 딸이다. 강백년(姜栢年)의 사위다.
1672년(현종 13) 별시 문과에 병과로 급제하여, 승문원부정자로 들어갔다가 시강원설서가 되었다. 이때 세자로 있던 숙종의 신임을 받아 1674년(숙종 즉위년)부터 검열·전적·정언·호조좌랑·수찬·의흥현감·교리·안악현감·이조좌랑 등으로 빠르게 진급하였고 항상 청요직에 있었다.
남인이 득세하자 관직에서 물러나 있다가 후에 승진하여 성균관사예·밀양부사·동래부사 등을 역임하였다. 당시 부산에 거주하던 왜인들의 작폐가 심하여 아무도 제어하지 못하였는데, 남익훈이 동래부사로 재임하면서 대마도주(對馬島主)와 교섭하여 옛날의 협약 준수를 촉구하고 왜관(倭館)에 비를 세워 불법행동을 금지시키고 단속을 엄하게 하였다.
그 뒤 승지·공조참의·나주목사·장례원판결사·여주목사·형조참의·장단부사·호조참판·동지의금부사·양주목사·경상도관찰사 등을 역임하고, 함경도관찰사를 지내던 중 임지에서 갑자기 죽었다. 관직에 있을 때는 모든 일을 직접 지휘, 감독하고 소홀함이 없어서 치적이 많았고 청렴, 근신하였다. 고대소설 「옥루몽(玉樓夢)」의 작자라는 설도 있다.