The fort is named as Anderitum, apparently meaning "great ford", in the Notitia Dignitatum, a list of Roman "dignities" (i.e. public offices) as of the 5th century. (An alternative spelling of Anderida or Anderita has also been proposed, but is disfavoured.)
The fort was built on what was then peninsula of land rising above the coastal marshes. The sea washed over what is now Pevensey Marshes surrounding Anderida on three sides, so giving a safe and sheltered landing point. This marshy inlet of the sea, extending inland as far as Hailsham, was studded with small areas of high land which remained as islands at high tide so giving the place-names of Rickney, Horse Eye, North Eye and Pevensey. All are derived from the Old English word īeg, meaning island.
Unlike at many other Roman forts, no civilian settlement or vicus appears to have been established outside the walls of Pevensey Castle; this was probably because the fort was at the end of a peninsula with limited room for additional construction.
The fort's construction has been dated to around 290, based on the dating of wooden piles which were found underpinning the Roman walls in an excavation carried out in 1994. Other Saxon Shore forts were built or reconstructed around this time as part of a systematic programme of improvements to the coastal defences of Roman Britain. The construction of the Saxon Shore forts has been linked to the raids that Saxon and Jute pirates (from what is now northern Germany and mainland Denmark) were mounting against communities along the North Sea and English Channel. An alternative explanation is that Anderitum was built to defend Roman Britain from Rome itself. Carausius, a Roman general who commanded the Classis Britannica (the Roman fleet based in the English Channel), revolted against Rome in 286 and declared himself emperor of Britain and northern Gaul. He was assassinated in 293 by his treasurer, Allectus, who was himself killed in 296 when the Roman emperor Constantius Chlorus invaded Britain to overthrow the usurper.
Coins of both Carausius and Allectus have been discovered buried in the foundations of the fort's walls. A later coin of 330–335 was found under a tower in the 1930s, suggesting that the fort may have undergone a major repair or reconstruction around that time. The usurpers had inherited an existing system of coastal defence – the earlier Saxon Shore forts – and may have decided to augment it with the construction of Pevensey Castle and its close contemporary, Portus Adurni (Portchester Castle).
Anderitum appears to have been a particularly important link in the Saxon Shore forts, which extended from Hampshire to Norfolk and may have been connected by intermediate watchtowers. The Notitia Dignitatum mentions a fleet that was presumably based there, the Classis Anderidaensis. It would probably have acted in coordination with naval units based on the other side of the Channel to intercept pirate ships passing through the Channel. Like the other Saxon Shore forts, Anderitum's position at a strategic harbour would have enabled the Romans to control access to the shoreline and prevent invaders from penetrating inland. It was linked by a road built in the late Roman period, probably at the same time as the fort.
It has been estimated that it took around 160,000 man-days to build the fort, equivalent to 285 men spending two years building it or 115 men over five years. At least four gangs of builders appear to have worked on the surviving sections of walls; each gang was given a stretch of about 20 metres (66 ft) at a time to build but executed the work in significantly different styles, for instance using differing numbers of tiled bonding-courses or ironstone facing in particular places. This may simply indicate varying levels of availability of construction materials at the time each segment was built, leading the gangs to use whatever supplies were available at that moment. The amount of construction material required was very large, equating to about 31,600 cubic metres (1,120,000 cu ft) of stone and mortar. It is not known how it was transported to the site, but that volume of material would have needed some 600 boat loads or 49,000 wagon loads, requiring 250 wagons pulled by 1,500–2,000 oxen to move it from the quarries to Pevensey. Given the scale of the requirements for land transportation, it seems more likely that the raw materials were instead moved by sea, though even this would have been a significant operation; it has been estimated that 18 vessels would have been needed for a continuous supply operation carried out over a season of 280 days.
The curtain wall was not all built at once but was constructed in segments, as can be seen from vertical breaks in the stonework which mark where sections met. The wall is built on top of complex foundations constructed from rubble and timber set into a ditch 15 feet (4.6 m) deep. Oak piles were driven into the trench and packed with flint and clay, above which a horizontal framework of oak beams was set with more flint and clay. The foundation was finally covered over with cement before the walls were built on top. Some of the timbers have survived, allowing archaeologists to date the fort through dendrochronology. Other dating evidence was discredited in the 1970s. An excavation in 1906–08 found shattered tiles stamped HON AUG ANDRIA, which were used to attribute Pevensey Castle's construction to the reign of the early 5th century Emperor Honorius. However, the use of thermoluminescence dating revealed that the tiles had been made around the time of the excavation. It is suspected that Charles Dawson, who has been blamed for the Piltdown Man hoax, was the author of the forged tiles.
Anderitum is recorded in the Notitia Dignitatum as the base of the praepositus numeri Abulcorum – an infantry unit or numerus of the limitanei or border forces. It also mentions army and naval units bearing the fort's name in connection with the Vicus Julius, in the Roman army in Gaul and stationed at Lutetia (modern Paris). This suggests that by the time the Notitia was written, the original garrison had been moved to Gaul and replaced with the numerus Abulcorum. The Abulci are mentioned in connection with the field army in Gaul and in the suppression of the rebellion of Magnentius in Pannonia Secunda in 351. It is not known whether their name is a geographical or functional one but their description by Zosimus suggests that they were an elite body of troops, who served both in the field army and, probably in the form of a single detachment, at Anderitum. They may have been foederati, troops raised from allied barbarian tribes and put under the command of a Roman prefect, or perhaps even a single band of warriors with their own leader. Similar numeri were recorded in the Notitia Dignitata as being stationed in other Saxon Shore forts.
When the Roman army retreated from Britain in 410, civilians appear to have moved into the abandoned fort, perhaps for protection against Saxon raiders, and its name continued to be used well into the Saxon period. In the entry for the year 491, the Anglo-Saxon Chronicle records that the Saxons Aelle and Cissa "besieged Andredadsceaster and slew all the inhabitants; there was not even one Briton left there." This event is now thought to have happened around 471 rather than the date recorded by the Chronicle (due to a dating error by Gildas, on whose work the Chronicle draws).
It is uncertain whether habitation of the fort continued after this event. The fort appears to have been resettled by about the middle of the 6th century by a Saxon community which left evidence of its occupation in the shape of pottery, glass and other items. By the late Anglo-Saxon period, Pevensey had become a well-established fishing port and producer of salt.
When William the Conqueror launched his invasion of England by landing at Pevensey Bay on 28 September 1066, his army sheltered for the night in a temporary fortification situated within the old Roman fort. The army left for Hastings the following day, en route to the Battle of Hastings. It was converted into a castle around 1100. Occupation continued until the Elizabethan era.