江戸時代「奈良奉行（南都町奉行）所」を前身として、1871年(明治4年)「奈良監獄署」が現在の奈良町大字西笹鉾に設立されます。司法省の設立と「監獄則」の布達と同時期の設立という点において、 奈良監獄は日本の司法とともに歩んできたと言っても良いでしょう。また、設立から約10年後に「奈良監獄分署」に改称された背景には、急速に日本の司法が変革を遂げたことがあると推測されます。
そして1901年(明治34年)に第1期監獄改築計画が議会を通過し、山下啓次郎を筆頭に 現在の場所へ「奈良監獄」の建築がスタートします。この起工を皮切りに、全国に「明治五大監獄」の建築がなされ、1909年(明治42年)、「奈良監獄」が現在の地に開設されるに至りました。
その後改装を繰り返しながら近代監獄としての役割を果たしてきた「奈良監獄」ですが、一時期は当時の定員数650人を大幅に上回る900人あまりの受刑者を収監していたという記録も残っています。
大正に入り、増加する少年犯罪に対応すべく1922年(大正11年)に「少年法」が公布されました。時を同じくして、「奈良監獄」から「奈良刑務所」と名称を改められます。

太平洋戦争の終戦翌年の1946年(昭和21年)、「奈良刑務所」が「奈良少年刑務所」と改称され、戦後の混乱期に起こった少年犯罪への対応に注力することとなります。1948年(昭和23年)には新少年法が公布、1949年(昭和24年)には犯罪者予防更生法を公布されるなど、「奈良少年刑務所」を取り巻く法律も改定が進んでいきます。国の法律だけではなく、「奈良少年刑務所」の内部でも、夜間教育やクラブ活動、出所後を見据えた職業訓練の種類なども多くあり、職業訓練を受けるために移送されてくる受刑者もいたそうです。平成に入ってからは、再犯防止に向けた情操教育や、性犯罪再犯防止指導拡大研究会が日本で初めて開催されるなど、全国に先駆けた取り組みが次々となされていきました。こうした取り組みに対して、国内外からの視察も多く受けていたという記録が残っています。