新宮市立図書館
公民館図書部と独立運動（1948-1953）
1948年（昭和23年）5月14日、新宮市公民館運営委員会は、公民館活動の一環として図書部を設置することを決議し、以前からの蔵書に加え市民からの寄贈図書と新刊書をもって公民館別館（旧丹鶴小学校講堂別館）内に図書部を開設した。活動を開始した図書部は狭く不便であったため、早くも1950年（昭和25年）4月14日には市当局に対し、移転を要望した。これを受けて市は旧軍人会館の一部を使用することを許可したが、図書部の全面移転を承認しなかったため、引き続き交渉することとなった。
1951年（昭和26年）1月26日には、公民館図書部から独立した図書館とするため、旧日本勧業銀行新宮支店を候補地として市に対して陳情した。続いて1952年（昭和27年）1月18日には公民館執行部委員会が和歌山県立図書館の分館を新宮へ誘致するためにも公民館から独立した図書館の設置を目指す運動を展開した。サービス面では1952年（昭和27年）10月1日より「夜間図書館」を開設して市民の利便性向上に努めた。
1953年（昭和28年）2月18日になり、図書館用地として寄付の申し出があった旧新宮税務署本館を受け入れることを新宮市議会が議決し、税務署の建物を新宮市新宮7696番地（横町一丁目1番地の6）へ移転・改築することと、その費用1,082,500円も同日中に決定した。移転先の土地は和歌山県から借用し、移転工事は随意契約で下地敏夫に発注した。工事は同年2月に始まり、同年7月末に完了した。
初代の図書館（1953-1974）
建物の移転工事の完了を受けて、1953年（昭和28年）8月1日から職員と学生アルバイトが図書や書棚などの搬入作業を行い、8月6日に公民館図書部から独立した新宮市立図書館が開館した。図書館は中心市街地という好立地に恵まれ、近畿地方の図書館の中では異例の画廊を持つ図書館として注目を浴び、市民の誇りともなった。この画廊では毎月、郷土出身画家の絵画展覧会を開催した。このほか読書会の開催や林業文庫の開設など和歌山県の図書館としては活発に活動していた。8月7日には閉館時間を午後9時に延長し、8月8日からは読書クラブの会員を対象として貸し出しを開始した。
1955年（昭和30年）6月に3代目館長に就任した岡嶋輝夫は、郷土研究の重要性を説き、郷土資料の収集強化と郷土史研究の推進のために熊野文化会（現・熊野地方史研究会）を設立した。熊野文化会は市立図書館内に設置し、会長に図書館長を当てることを会則で定めており、会の活動は図書館と一体的に行われた。また熊野文化会の機関誌として1958年（昭和33年）に『熊野誌』を創刊した。
岡嶋の後任の浜畑栄造も岡嶋館長の路線を踏襲し、郷土資料の収集の推進や『熊野誌』で大石誠之助特集を組むなど精力的に活動した。ところがこの大石特集が新宮市教育委員会で「市民に共産主義、無政府主義を宣伝するようなもの」と見なされ、さらに浜畑館長が大石の遺稿集の発刊を企画したことから、教育委員会は事実上の「更迭」となる再任拒否を決定した。後任の館長の選考は難航し、5代目館長が任命されたのは、浜畑館長「更迭」から2か月後のことであった。館長更迭事件は当時の市立図書館の一般職員さえ十分に把握しておらず、一般市民は浜畑が地元紙紀南新聞に投稿した「市民に訴える」と題した文章を読んで初めて知るところとなった。和歌山県の図書館界でも一部の人が新宮市立図書館の新館長がなかなか決まらないということを認知していただけであった。なお当時の館長職は名誉職としての側面が強く、館長手当は月2,500円だったという。
新宮市立図書館の開館後も、中心市街地から離れた三輪崎や佐野、高田などから図書館を訪問するのは容易ではなかったため、それぞれの地区に「文庫」が開設された。三輪崎では三輪崎青年会が1962年（昭和37年）11月15日に読書週間の記念事業として三輪崎文庫を設立し、佐野では佐野婦人会が1969年（昭和44年）2月に婦人会長宅の玄関先に佐野文庫を設立した。三輪崎文庫は運営にあたった青年会員の仕事の都合で、佐野文庫は主な利用層と見なしていた成人女性が昼は勤労、夕方は家事と多忙であったため、存続が危うい状態であった。一方、新宮市公民館高田分館に設けられた高田文庫は新宮市役所の高田支所長が管理運営にあたったため安定していた。
1969年（昭和44年）9月、市民有志が「市立図書館建設促進委員会」を立ち上げ新図書館建設運動を展開した。1971年（昭和46年）3月になって紀南学園跡地（新宮6634番地の4）を新図書館の建設地とすることが決定した。
2代目図書館（1974-）
1973年（昭和48年）11月26日、新図書館の建設工事が始まり、1974年（昭和49年）7月31日に竣工、同年11月1日に開館式が挙行された。同時に佐藤春夫文庫が設置されている。1977年（昭和52年）2月に大桑勇から自動車文庫用のバスが寄贈され、同年9月から自動車文庫による市内巡回が開始された。また、この自動車文庫には「なかよし号」の愛称が付与された。
新図書館開館後も、子供向けに図書の貸し出しや読み聞かせを行う私設図書館「地域文庫」が市内各所に開設された。その先駆けとなったのは1979年（昭和54年）に開館した「たけの子文庫」で、小学校教諭を中心に地域の女性が新宮市佐野の民家で始めたものである。地域文庫の取り組みは1990年代以降縮小し、2013年（平成25年）までに新宮市内ではすべて閉館した。
1989年（平成元年）に中上健次コーナーを1991年（平成3年）に南方熊楠コーナーと山本七平コーナーを設置し、1998年（平成10年）3月に中上健次コーナーとは別に中上健次資料収集室を開設した。2000年（平成12年）には丹鶴同窓会付属図書館の開館から100年となるのを記念して、「図書館百周年記念事業」を実施した。同年10月、和歌山県内の図書館の蔵書情報を一括検索できる「和歌山地域コンソーシアム図書館」が発足し、市町村立図書館として唯一参加した。
2003年（平成15年）3月13日にコンピュータによる蔵書管理を開始した。2004年（平成16年）6月より4か月検診の際に絵本の読み聞かせを開始し、2005年（平成17年）7月からはブックスタート事業を始めた。これらの活動と前後して2004年（平成16年）4月23日に子どもの読書活動優秀実践図書館として文部科学大臣表彰を受けた。
2011年（平成23年）9月4日、台風12号が新宮市を襲い、市立図書館でも浮島書庫の浸水で1,624冊を処分する被害を受けた。本館では断水や回線の寸断による図書館システムのダウンという被害があり、被災した市民が借用して流失・紛失した図書については弁償を免除した。被災した市民の中には自動車文庫の常連利用者もおり、特に相賀地区では唯一の女性利用者がこの台風に伴う豪雨災害で行方不明となったため、自動車文庫の相賀地区への乗り入れを取りやめることになった。この豪雨災害に関しては『熊野誌』第61号で特集された。
2011年（平成23年）度に緊急雇用創出事業を利用して図書館の蔵書にICタグを貼り付け、同年度から蔵書のIC管理を開始し、2014年（平成26年）6月1日には館内でWi-Fiサービスの提供を開始した。2015年（平成27年）秋には読書週間に合わせて「すべての本にその読者を」と題した企画を実施し、コンピュータ導入から同年7月31日までに一度も貸し出されたことのない597冊の中から100冊を厳選して展示した。その中には映画化もされたマイケル・モーパーゴ『戦火の馬』などがあった。
文化複合施設の建設計画
新宮市では2008年（平成20年）10月3日に新宮市立図書館建設準備委員会を設立して新図書館の建設を検討してきたが、2011年（平成23年）2月の文化複合施設基本計画策定により、図書館建設計画は文化複合施設の建設計画に包摂されることとなった。2014年（平成26年）に市立図書館が行ったアンケートでは、蔵書量と施設・設備に関して不満に感じる利用者が多いことが明らかになっている。
2014年（平成26年）8月、国土交通省がコンパクトシティ推進のために「都市再構築戦略事業」を展開し、新宮市の事業が採択された。新宮市が提示した事業は5つあったが、その中核事業が丹鶴小学校跡地への文化複合施設の建設であり、文化複合施設には図書館、文化ホール、熊野学センターの3つを整備する計画で、事業費予想は53億1200万円、2018年（平成30年）度に完成予定とされた。2015年（平成27年）3月には公募型プロポーザル方式で山下設計関西支社・金嶋一級建築設計事務所共同企業体の案が最優秀として公開された。この案では大小のホールから成るホール棟、図書館と熊野学アーカイブから成る図書館棟、研修室などから成るスタジオ棟の3棟が中央の「熊野ひろば」を取り囲むというもので、熊野学センターは3棟に機能を分散するというものであった。その後、熊野学センターを独立棟とするよう設計案が変更され、熊野学センター1階を熊野ひろば、2階を熊野学アーカイブと中上健次コーナーにすることとなった。
2015年（平成27年）7月、文化複合施設の建設予定地で埋蔵文化財の試掘調査が行われ、江戸時代の武家屋敷の道路跡が発見されたことから、予定外の1億円の発掘費がかかることとなった。さらに田岡実千年市長が当初示した完成後の維持費を年間1億円以内とするという方針が、他の自治体の同種施設の比較から実現できないことが判明するなど、計画に暗雲が立ち込め始めた。そこで田岡市長は2016年（平成28年）2月に熊野学センターの建設取りやめを文化複合施設管理運営検討委員会に報告した。総事業費が当初計画を大幅に上回る見通しとなったための措置で、熊野学センターが担う予定だった機能の一部を図書館などに持たせることで、計画通りの予算内での建設を進める方針を示したのであった。これに対して検討委員の中からは「熊野学センターから始まった文化複合施設計画であるので、熊野学センター抜きはありえない」という旨の意見が出された。
2016年（平成28年）8月には文化ホールを西側に移設することで発見された遺跡の保存を図ることと、都市再構築戦略事業の2年延長を求め2020年度完成予定とすることが新宮市議会で田岡市長から発表された。2017年（平成29年）4月には文化複合施設の設計業務の再委託が行われた。
充実した郷土資料
蔵書総数10万冊程度の小規模な図書館でありながら、2万点もの郷土資料を所蔵している。（2015年度時点で28,132点を所蔵する。）郷土資料の充実ぶりは新宮市立図書館の特徴としてよく知られており、豊富な資料を求めて新宮市周辺のみならず、和歌山県外からも来館者が訪れている。収集対象資料は新宮市のみならず、熊野地方広域に及ぶ。
郷土資料の蓄積は3代目の館長・岡嶋輝夫によってその基礎が築かれた。岡嶋館長は「新しいものが物を言う時代こそ、時代をさかのぼって文化資料を収集し記録を残すことも図書館の使命である」と考え、1957年（昭和32年）度の図書館費の項目として「郷土研究費」を設け、郷土資料収集と郷土研究を推進した。岡嶋館長退任後も郷土資料の収集は続けられ、レファレンスへの対応のために収集資料を増やしていった。
所蔵する郷土資料は、大逆事件（幸徳事件）において熊野地方の中心人物とされた大石誠之助に関する資料のほか、佐藤春夫、西村伊作、東基吉・くめ夫妻、村井正誠、畑中武夫、世耕弘一、中上健次、田村さと子、鈴木理策ら新宮市出身ないしは新宮市ゆかりの人物に関する資料、両親が三輪崎町（現・新宮市三輪崎地区）出身の山本七平に関する資料、熊野信仰・熊野古道に関する資料、熊野地方の山林に関する資料、新宮領主・水野忠央に関する資料、徐福伝説に関する資料など多岐に渡る。
これらの膨大な郷土資料の検索利便性を高めるために、新宮市立図書館では『郷土資料件名事項目録』を作成している。同目録は、特定のキーワードについて言及する郷土資料を件名別に収録したものであり、紙媒体の冊子のほか、公式サイトでも公開している。
中上健次資料収集室
市立図書館3階に書庫を改造した「中上健次資料収集室」がある。資料収集室の面積は22m²で、机・椅子・書架を配置する。1989年（平成元年）に中上健次コーナーが開設された後、1996年（平成8年）から1997年（平成9年）にかけて『中上健次全集』が刊行されたことと1996年（平成8年）8月に新宮市で「中上健次展」が開催されたことを契機として発足した。発足当初の所蔵資料は中上の著書や関連書など650冊であった。中上健次資料収集室の開室を記念して、中上健次を特集した『熊野誌』第39号が増刷された。
事前予約すれば、専門の担当者による応対を受けることができる。2015年（平成27年）度の来室者数は148人、所蔵資料数は3,202点。
熊野誌
『熊野誌』（くまのし）は、新宮市立図書館が毎年1回刊行する雑誌。1958年（昭和33年）3月に熊野文化会（現・熊野地方史研究会）の機関誌として創刊し、2013年（平成25年）で第60号を迎えた。『熊野誌』は創刊号で「熊野地方についていろんなことを書き誌したものといふ意味である」と述べている通り、熊野地方に関係すれば何でも掲載するという方針で編集しており、専門性の高い研究論文から一般市民にも理解しやすいものまで幅広く扱う。熊野地方に関する内容であれば住民でなくても投稿を受け付けている。図書館職員が寄稿することもあり、第62号（2015年）では地域文庫の歴史について嘱託職員がまとめた記事を掲載している。
適宜特集が組まれ、第6号（1961年）は大石誠之助、第59号（2012年）は中上健次、第60号（2013年）は熊野の自然、第61号（2014年）は2011年の紀伊半島大水害が特集された。
『熊野誌』は熊野地方の書店などで一般販売されるほか、新宮市立図書館が通信販売を行っている。
県境の図書館
新宮市は三重県との境界に近く、三重県側からの来館者も少数ながら存在する。三重県側には紀宝町立鵜殿図書館や熊野市立図書館などが近隣にあり、新宮市立図書館より施設が新しく新刊数や雑誌の種類が多いという住民の評価があり、新宮市立図書館と併用する新宮市民も存在する。
2013年（平成25年）3月には三重県南部の本を展示するという企画を開催し、御浜町阿田和が登場する紀和鏡のデビュー作『Aの霊異記』や紀宝町出身の法医学者・古畑種基の自伝など70冊を紹介した。
自動車文庫「なかよし号」
1977年（昭和52年）2月に三重県鵜殿村（現・紀宝町鵜殿）に居住していた大桑勇（オークワ創業者）から自動車文庫用の車両の寄贈を受け、同年9月から自動車文庫の運行を開始した。この車両は同年8月に公募により「なかよし号」と名付けられた。運行当初は木ノ川・佐野、南桧杖・三輪崎、相賀・高田の3コースが設定された。
車両は1993年（平成5年）に2代目「なかよし号」へ交代し、2006年（平成18年）4月からは3代目に移行している。3代目なかよし号は3.5tトラックを改造したもので、事業費2570万円は日本宝くじ協会から全額助成を受けた。車体には馬場のぼる『11ぴきのねこ ふくろのなか』に登場するネコたちが描かれており、2代目なかよし号の3倍に相当する3,000冊を積載することができる。3代目なかよし号への移行と同時に平成の大合併で市域の一部となった旧熊野川町内でも巡回を開始した。
2011年（平成23年）の豪雨災害時には、本館の図書館システムがダウンしたため、自動車文庫の端末を利用した図書の貸し出しが行われた。2015年（平成27年）度時点の巡回地点は9か所、利用者数は1,726人、貸出冊数は12,986冊。
交通
2014年（平成26年）の利用者アンケートによると、49%が自動車、31%が二輪車（自転車・オートバイ）、13%が徒歩で来館しており、公共交通機関の利用者はわずかである。（なお徒歩来館者には自動車文庫の利用者を含む。）
JR東海/JR西日本紀勢本線（きのくに線）新宮駅から徒歩約5分である。