The Rochester diocese was founded by Justus, one of the missionaries who accompanied Augustine of Canterbury to convert the pagan southern English to Christianity in the early 7th century. As the first Bishop of Rochester, Justus was granted permission by King Æthelberht of Kent to establish a church dedicated to Andrew the Apostle (like the monastery at Rome where Augustine and Justus had set out for England) on the site of the present cathedral, which was made the seat of a bishopric. The cathedral was to be served by a college of secular priests and was endowed with land near the city called Priestfields.
Under the Roman system, a bishop was required to establish a school for the training of priests. To provide the upper parts for music in the services a choir school was required. Together these formed the genesis of the cathedral school which today is represented by the King's School, Rochester. The quality of chorister training was praised by Bede.
The original cathedral was 42 feet (13 m) high and 28 feet (8.5 m) wide. The apse is marked in the current cathedral on the floor and setts outside show the line of the walls. Credit for the construction of the building goes to King Æthelberht rather than St Justus. Bede describes St Paulinus' burial as "in the sanctuary of the Blessed Apostle Andrew which Æthelberht founded likewise he built the city of Rochester."
Æthelberht died in 617 and his successor, Eadbald of Kent, was not a Christian. Justus fled to Francia and remained there for a year before he was recalled by the king.
In 644 Ithamar, the first English-born bishop, was consecrated at the cathedral. Ithamar consecrated Deusdedit as the first Saxon Archbishop of Canterbury on 26 March 655.
The cathedral suffered much from the ravaging of Kent by King Æthelred of Mercia in 676. So great was the damage that Putta retired from the diocese and his appointed successor, Cwichelm, gave up the see "because of its poverty".
In 762, the local overlord, Sigerd, granted land to the bishop, as did his successor Egbert. The charter is notable as it is confirmed by Offa of Mercia as overlord of the local kingdom.
Following the invasion of 1066, William the Conqueror granted the cathedral and its estates to his half-brother, Odo of Bayeux. Odo misappropriated the resources and reduced the cathedral to near-destitution. The building itself was ancient and decayed. During the episcopate of Siward (1058–1075) it was served by four or five canons "living in squalor and poverty". One of the canons became vicar of Chatham and raised sufficient money to make a gift to the cathedral for the soul and burial of his wife, Godgifu.