The proposal for the construction of Cellular Jail was devised in 1890 on the recommendations of the Lyall and Lethbridge committee, but it was completed only in 1906.

Before the Cellular Jail was constructed, prisoners used to be housed in barracks in Port Blair, the Ross Island and also in concrete structures on Viper Island. The Lyall and Lethbridge Committee consisting of CJ. Lyall of Bengal Civil Service and Surgeon Major A.S. Lethbridge, inspector general of jails, Bengal inspected the penal settlement at Port Blair in January 1890. Members of this committee reached the Andamans by S.S. Peshwa on 20th January 1890. They stayed there for approximately two weeks and left Port Blair by the same ship on 7th February 1890. The detailed report was submitted by them to the British government on 26th April 1890, a copy of which is available in National Archives, (Home, Port Blair 1890 No. 74 to 78). Colonel Cadell was the jail superintendent during that time. Among other things, the committee suggested in their report to increase the harshness of confinement in the Andamans by keeping the convicts confined in the cells of a restricted area. The doctrine, followed was that a "prison regime must be punitive and humiliating even more dreadful than hangman's noose" so as to employ deterrence through fear both against those subjected to it and for the 'potential dangers' in general. With this objective, the proposal of the committee to construct the Cellular Jail was approved by the government.

Originally, the Andaman and Nicobar Manual Settlement Order No. 423 dated 13th September, 1893 was issued for taking up the work of constructing the Cellular Jail right away, as the completion of the jail was considered to be a matter of great urgency. It was to be completed on priority so as to receive the first batch of convicts in October 1896. The jail was to hold 600 prisoners and was to be built at an estimated cost of Rs. 5,17,352 (cash expenditure Rs. 95,881) with McQullen, sub-engineer serving as in-charge of the construction work. But the actual construction of the Cellular Jail was taken up in October 1896.

To speed up the construction work, human resource convicts from different stations like Viper, Navy Bay, Phoenix Bay, Brichgunj, Dundas point etc. were dictated to work in the jail building. At the same time, the southern divisional officer was directed to arrange 20,000 cubic feet of stone broken up every month by the Viper inmates there. Apart from locally available material, building material was also brought here in enormous quantities from Burma. Sir Richard Temple was the Chief commissioner of Andamans. By 1897 although around 400 cells of the Cellular Jail were ready for occupancy, yet it could be completed only in 1906. It was built on the seacoast at Atlanta Point in Aberdeen at a height of 60 feet from the sea level.

The Cellular Jail was a 'pucca' brick structure giving the appearance of a massive fortress. Almost all the political prisoners who have written their memoirs have made reference to the structure, its location and the inner details of the jail. Bejoy Kumar Sinha compared it to the "England's manorial castles that had imprisoned many who were for the march of history against the decaying, parasitic feudalism".