1451년(문종 1) 사마시(司馬試)에 입격하였고, 1454년(단종 2)에 문과에 급제하였다. 신말주가 문과에 급제하였을 때 셋째 형 신숙주는 도승지(都承旨)로 있었다. 집에서 과거 급제 축하연을 벌였는데, 단종이 술 30병을 내렸다. 세조 즉위 이후 원종공신(原從功臣) 2등에 녹훈되었다. 이후 사간원 우정언(右正言)과 우헌납(右獻納)에 임명되어 대간으로 활동하였다.
세조 재위기에 예조정랑(禮曹正郞), 사헌부(司憲府) [집의(執義)], 사간원(司諫院) 사간(司諫), 대사간(大司諫), 형조참의(刑曹參議) 등을 역임하였다. 성종이 재위한 이후에는 전주부윤(全州府尹), 진주목사(晉州牧使), 창원 도호부사(昌原 都護府使), 경상우도 병마절도사(慶尙右道 兵馬節度使) 등의 외직을 담당하였다. 1487년(성종 18) 다시 사간원 대사간으로 임명되었다. 하지만 정확하지 않았던 소문으로 김석(金磶)의 추문(推問)을 주장하다가 스스로 잘못을 깨닫고 죄를 청해 좌천되었다. 2개월 후 다시 절충장군(折衝將軍) 첨지중추부사(僉知中樞府事)로 임명되었다.
야사에는 신말주가 단종이 폐위된 이후 순창(淳昌)에 머물면서 벼슬하기를 원하지 않았다는 기록도 있다. 하지만 세조 대 2등 원종공신으로 녹훈되었고, 계속 대간의 역할을 수행하다가 대사간까지 맡았던 기록이 확인된다. 따라서 신말주가 단종 폐위 이후 벼슬에서 물러나 관직 생활을 피하였다는 이야기는 그의 생애와 관련된 정확한 서술로 보기는 어렵다.