In the 1080's, Alan the Red, one of William Conqueror's top soldiers and trusted adviser, was given large amounts of land as a reward for his services. He chose to build his principal castle and residence on a high cliff above the River Swale. The castle was one of the earliest in England to be built of stone and consisted of a high stone wall, apart from in the south where there was probably a timber palisade on the edge of the cliff above the river, and a great hall, named Scolland's Hall after Earl Alan's steward. Scolland Hall was an early form of keep, a fortified building that served as a residence and a stronghold. Other buildings in the compound would have been made out of wood.

From 1146-71 the castle was held by Conan 'the little', Earl of Brittany, who added the massive new tower keep, though it was probably finished by King Henry II who controlled the castle after Conan's death in 1171. Henry strengthened the castle walls and towers, replacing the wooden palisade at the top of the cliff with a stone wall, and added a barbican with moat and drawbridge in front of the keep.

The last major building campaign was in the fourteenth century when new chambers and a new chapel were added to the north end of Scolland's Hall by Duke John of Brittany.

By the early years of the sixteenth century parts of the castle were in a state of disrepair. The castle was no longer of military value and it was too old fashioned to be used as a residence.

In 1855 the castle was leased from the Duke of Richmond for use as the headquarters of the North York Militia. The Great Court was cleared of debris and a new building (now demolished) was built on its western side to accommodate staff and for use as offices and storerooms. A detention block of eight cells was added just inside the castle entrance. In 1910 the castle was placed in the care of the Office of Works, but it returned to military use during the First and Second World Wars.