He was an illegitimate son of Thomas Tunstall of Thurland Castle, Lancashire; his legitimate half-brother, Brian Tunstall, was killed at the Battle of Flodden in 1513. Cuthbert seems to have studied at Oxford, at Cambridge and at Padua, and became a distinguished scholar, winning favourable comment from Erasmus. Having held several livings in quick succession, he became chancellor to William Warham, Archbishop of Canterbury, in 1511, and was soon employed on diplomatic business by King Henry VIII and Cardinal Wolsey, being sent to Brussels in 1515 and to Cologne in 1519. He was present during the famous Diet of Worms in 1521.
In 1516 he had been made Master of the Rolls; in 1521 he became Dean of Salisbury, in 1522 Bishop of London, and in 1523 keeper of the privy seal. For Henry VIII he negotiated with Charles V, Holy Roman Emperor, after the Battle of Pavia in 1525, and he helped to arrange the Peace of Cambrai in 1529. In 1530 he succeeded Wolsey as Bishop of Durham. However, Tunstall's religious views soon caused anxiety. He adhered firmly to the traditional teaching of the Church, but after some hesitation he accepted Henry as its head and publicly defended this position. In 1537 the bishop was appointed president of the new council of the north, but although he was often engaged in negotiations with the Scots, he found time to take part in other public business and to attend parliament, where in 1539 he participated in the discussion on the bill of six articles. Although he disliked the religious policy pursued by the advisers of King Edward VI and voted against the first act of uniformity in 1549, he continued to discharge his public duties without molestation until after the fall of Edward Seymour, 1st Duke of Somerset; then in May 1551, he was placed in custody.
A bill charging Tunstall with treason was introduced, but the House of Commons refused to pass it; he was, however, deprived of his bishopric in October 1552. On the accession of Mary in 1553 he was released and again became Bishop of Durham, but during this reign he showed no hostility to the Protestants. When Elizabeth I came to the throne he refused to take the oath of supremacy, and would not help to consecrate Matthew Parker as Archbishop of Canterbury. He was arrested, and was a prisoner at Lambeth Palace when he died.
Among Tunstall's writings are De veritaie corporis et sanguinis domini nostri Jesu Christi in eucharistia (1554); and De arte supputandi libri quattuor (1522). The bishop's correspondence as president of the council of the north is in the British Museum.