He was born at Baldovie near Montrose, Angus, the youngest son of Richard Melville (brother to Melville of Dysart); his father died at the Battle of Pinkie in 1547, fighting in the van of the Scottish army. Andrew's mother died soon after, and the orphan was cared for by his eldest brother Richard (1522–1575).
At an early age Melville began to show a taste for learning, and his brother did everything in his power to give him the best education. He learned the rudiments of Latin at the grammar school of Montrose, after leaving which he learned Greek for two years under Pierre de Marsilliers, a Frenchman whom John Erskine of Dun had persuaded to settle at Montrose; such was Melville's proficiency that on going to the University of St Andrews he astonished the professors by using the Greek text of Aristotle, which no one else there understood. On completing his course, Melville left St Andrews with the reputation of "the best poet, philosopher, and Grecian of any young master in the land."
In 1564, at nineteen years of age, he set out for France to complete his education at the University of Paris. He applied himself to Oriental languages, but also attended the last course of lectures delivered by Adrianus Turnebus, professor of Greek, as well as those of Petrus Ramus, whose philosophical method and plan of teaching Melville later introduced into the universities of Scotland. From Paris he went to Poitiers (1566) to study civil law, and though only twenty-one was apparently at once made a regent in the college of St Marceon. After three years, however, political troubles compelled him to leave France, and he went to Geneva, where he was welcomed by Theodore Beza, at whose instigation he was appointed to the chair of humanity in the academy of Geneva.
In addition to teaching, Melville continued to study Oriental literature, and in particular acquired from Cornelius Bertram, one of his brother professors, a knowledge of Syriac. While he lived at Geneva the massacre of St Bartholomew in 1572 drove immense numbers of Protestant refugees to that city, including several of the most distinguished French men of letters of the time. Among these were several men learned in civil law, and political science, and associating with them increased Melville's knowledge and enlarged his ideas of civil and ecclesiastical liberty. In 1574 Melville returned to Scotland, and almost immediately received the appointment of Principal of the University of Glasgow, and began its renewal.
Melville set himself to establish a good educational system. He enlarged the curriculum, and established chairs in languages, science, philosophy and divinity, which were confirmed by charter in 1577. His fame spread, and students flocked from all parts of Scotland and beyond. He assisted in the reconstruction of the University of Aberdeen in 1575, and to do for St Andrews what he had done for Glasgow, he was appointed Principal of St Mary's College, St Andrews, in 1580. His duties there comprised the teaching of theology, Hebrew, Chaldee, Syriac and Rabbinical languages.
Melville created a fashion for the study of Greek literature. The reforms, however, which his new modes of teaching involved, and even some of his new doctrines, such as the non-infallibility of Aristotle, brought him into conflict with other teachers in the university. He was Moderator of the General Assembly in 1578, and took part in the organisation of the Church and the Presbyterian method. Troubles arose from the attempts of the court to force a system of episcopacy upon the Church of Scotland, and Melville prosecuted one of the Tulchan Bishops (Robert Montgomery, d. 1609). For this he was summoned before the Privy Council in February 1584, and had to flee into England to escape a charge of treason.
He returned to Scotland in November 1585 after an absence of twenty months, and in March 1586 resumed his lectures in St Andrews, where he continued for twenty years; he became Rector of the University in 1590. During the whole time he protected the liberties of the Scottish Church against all encroachments of the government. That in the main he was fighting for the constitutionally guaranteed rights of the Church is generally accepted. The chief charge against Melville is that his fervour often led him to forget the reverence due to an "anointed monarch." When the king acted in an arbitrary and illegal manner he needed the reminder that though he was king over men he was only "God's silly vassal." Melville's rudeness (if it is to be called so) was the outburst of just indignation from a man zealous for the purity of religion and regardless of consequences to himself.
His nephew James Melville, who was present, records the famous statement he made in Falkland in private to King James VI of Scotland, later to become King James I of England . Calling him "God's sillie vassal" and taking him by the sleeve, he said,
"Sir, we will humblie reverence your Majestie always, namlie in public, but sen we have this occasioun to be with your Majestie in privat, and the treuthe is, yie ar brought in extream danger bathe of your lyff and croun, and with yow, the country and Kirk of Christ is lyk to wrak, for nocht telling yow the treuthe, and giffen of yow fathfull counsall, we mon (must) discharge our dewtie thairin, or els be trators bathe to Christ and yow! And thairfor Sir, as divers tymes befor, sa now again, I mon tell yow, thair is twa Kings and twa Kingdomes in Scotland. Thair is Chryst Jesus the King, and his Kingdome the Kirk, whase subject King James the Saxt is, and of whose kingdome nocht a king, nor a lord, nor a heid, bot a member! And they whome Chryst hes callit and commandit to watch over his Kirk, and govern his spirituall kingdome, hes sufficient powar of him, and authoritie sa to do, bathe togidder and severalie; the quhilk na Christian King or Prince sould control and discharge, but fortifie and assist, utherwayes nocht fathfull subjects nor members of Chryst."
In 1599 he was deprived of the rectorship, but was made dean of the faculty of theology. The close of Melville's career in Scotland was at length brought about by James in characteristic fashion. In 1606 Melville and seven other clergymen of the Church of Scotland were summoned to London in order "that His Majesty might treat with them of such things as would tend to settle the peace of the Church." The contention of the whole of these faithful men was that the only way to accomplish that purpose was a free Assembly. Melville delivered his opinion to that effect in two long speeches with his accustomed freedom, and, having shortly afterwards written a sarcastic Latin epigram on some of the ritual practised in the chapel of Hampton Court Palace, and some eavesdropper having relayed it to the king, he was committed to the Tower of London, and detained for four years. On being freed, but refused permission to return to his own country, he was invited to fill a professor's chair in the Academy of Sedan, and there he spent the last eleven years of his life.