域多利监狱建于1841年，位处于域多利市中心，近望维多利亚港。早期的域多利监狱主要是收押钱债犯人，等候审判的犯人和被判处流放刑而等候安排船期之犯人。当香港取消流放刑后，囚犯的数目跟香港人口增长率一样同步增长。域多利监狱在二战前多被称为香港监狱或域多厘监狱，归「提牢厅」〔即现时之惩教署〕管辖。

由于香港是英国殖民地，监狱管冶主要依据英国殖民地办公处的指引来执行，囚犯须按年龄，性别，所犯的罪行和刑期的长短来分类。由于这个分类导致域多利监狱在安排住宿上及在收押犯人上不断的产生问题。监狱为应付囚犯住宿挤逼的问题而不断需要加建，从监狱早期的图则中可以见到域多利监狱在不同时期的变更。

早期的提牢厅是归由警务处所管辖，直至1858年警务处指派了一名「域多利监狱长」管冶监狱。由1863年起域多利监狱主管改名为域多利监狱监督，这人选是直接由英国政府委派。1863年监狱长更要负责管治一批住在狱船上的囚犯，他们负责在昂船州上兴建一所新的监狱，这项监狱工程于1866年被腰斩。

在1920年12月31日监狱署正式地脱离警务处的管辖，独立负起管理监狱及囚犯的工作。监狱狱长成为监狱署的首长。自1938年起这职位再改名为监狱署署长。

赤柱监狱，(时称香港监狱)，于1937年开幕后，域多利监狱所有囚犯都被迁往赤柱，而域多利监狱于同年9月26日结役。由于赤柱监狱过份挤逼，部份域多利监狱于1939年10月16日重新开放，由于当时它只接收还押犯人，所以改名叫域多利收押所。

域多利收押所于1941年二战时被停用，而大部份监狱建筑物亦于日军佔领时遭到严重破坏，战后部份域多利监狱建筑圽在被复修后于1946年7月重新遇运作。及后域多利监狱在不同时期仍作出不同情度的复修，直至目前的模样。

域多利收押所于1965年开始用作为收押中心，所有男性犯人都先被收押在此监狱，经分类后再转送到其他院所。自荔枝角收押所于1977年12月1日启用后，域多利收押所再被用作为一所中度设防的监狱，改名为域多利监狱。

监狱署于1982年改名为惩教署，为更贴切地反映部门对囚犯的职责为监管-「惩」和更生-「教」并重。

1997年香港成为特别行政区并开展新的一页，这年亦是香港收容越南难民的最后一年。随着最后一所禁闭式难民营于1998年关闭后，所有越南羁留犯都被羁留在域多利监狱，等侯遣返回越南。

为应付香港不断增加的女性囚犯，域多利监狱于2001年1月把部份囚仓改为收容女性犯人。域多利监狱在香港有它独特的角色，它不单只是监狱亦是收容不同类别，性别犯人的收押中心，更是非法入境者和越南船民的羁留中心及一般外籍犯人在服刑完毕后等候遣返的收容中心。

从2005年8月起惩教署接收了青山湾入境事务中心后，所有非法入境者及等候遣返的人士都从域多利监狱搬到这中心。域多利监狱又再恢复为只接收男女犯人的监狱。