The first documentary mention of the castle is in 1290 when Edward I of England appointed Brian FitzAlan as custodian of the Castles of Dundee and Forfar. Therefore it was erected sometime before 1290, most probably of a Motte and Bailey type, probably started as a timber construction, surrounded by a defensive timber palisade, later replaced by stone buildings, curtain walls and towers, built on the very noticeable hill of Black dolerite rock jutting into the Tay, an impressive situation guarding the harbour. There is mention of it being surrounded by a large ditch with a drawbridge. Early Dundee historians argue that it was extensive and maintained at least 130 knights and horsemen within its walls, evidence of this comes from the exchequer rolls of England regarding provisions sent to the Castle during the reigns of Edwards I and II.
The Castle was seized by English Troops at the beginning of the Wars of Independence in 1296, then seized back by the Scots under Sir Alexander Scrymgeour, for this he was made hereditary Constable of the Castle by William Wallace in 1298.
It may have been demolished by the Scots on the order of King Robert sometime at the beginning of the 14th Century, it was certainly gone by 1318. The hill on which it was built still survives, now occupied by the imposing St Paul's Cathedral, the black rock still visible behind some of its walls and in the basements of some stores lining Castle Street, this street was constructed during the early 19th Century by blasting through the hard black rock to provide a new access to the harbour.