He was born at Baldovy near Montrose, 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, 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 stufy 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 Glasgow University, which had fallen into an almost ruinous state, the college having been shut and the students dispersed.
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, till there was no room for them. He assisted in the reconstruction of Aberdeen University in 1575, and in order 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 1582, and took part in the organization 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 in order to escape a charge of treason.
After twenty months he returned to Scotland in November 1585, 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.
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 thai effect in two long speeches with his accustomed freedom, and, having shortly afterwards written a sarcastic Latin epigram or 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 University of Sedan, and there he spent the last eleven years of his life.