Fort Madalena was built between December 1875 and 1881 at a cost of £9,400. The Fort was located on the Eastern end of the Victoria Lines and also provided coverage of the coastline adjacent to Pembroke. This pentagonal Fort was surrounded by a dry moat which had four two-storey counterscarp galleries. Five 32-pdr SB BL guns were mounted in these counterscarp galleries for local defence. There was a large earthen traverse (parados) down the centre of the Fort which split the gun line from the barracks and store rooms.
Initial armament was 64-pdr RML guns, some on disappearing carriages. There was also some 40-pdr RBL guns on field carriages, which may have been available for deployment on the Victoria Lines. Three 11-inch RML guns were added but in 1886. At this time it was recommended that two 6-inch QF guns and a heavy BL gun (10-inch) be added.
The Nicolson and Goodenough report recommended that the five 32-SB BL guns in the counterscarp galleries be removed. The 3-pdr guns on field carriages to be replaced by 6-pdr and the 11-inch RML needed to remain.
In 1892 Fort Madalena was upgraded to mount four 6-inch BL guns on HP mountings. The three 11-inch RMLs to be removed and all but one of the 40-pdr RBLs.
In 19055 the armament was again revised. The old 6-inch guns were removed and replaced by two 6-inch Mark VII BL guns. An additional two 9.2-inch Mark X BL guns were mounted in a new works outside the original moat and facing seawards.