Merriam-Webster's Eleventh Collegiate Dictionary (2003) gives a straightforward summary of the etymology of trinity:
Trinity n {M[iddle] E[nglish] trinite, fr. A[nglo-]F[rench] trinité, fr. L[ate] L[atin] trinitat-, trinitas state of being threefold, fr. L[atin] trinus threefold} (13c) 1 : the unity of Father, Son, and Holy Spirit as three persons in one Godhead according to Christian dogma} ...
What this summary tells you is that the word Trinity appeared in English from Middle English in the thirteenth century; that it was derived ultimately from the Latin word for "threefold," and that its original meaning in English was the religious one indicating the three-in-oneness of Jesus/God/Holy Ghost.
The earliest instance that a Google Books search for "Holy Trinity" turns up is from Articles agreed upon by the Bishops, and other Learned and Godly Men, in the last Convocation at London, in the year of our Lord 1552. To root out the Discord of Opinions, and establish the Agreement of TRUE RELIGION. Published By the Kings Majesties Authority, 1553. (1553):
Of Faith in the Holy Trinity.
There is but one living and true God, and he is everlasting, without body, parts, or passions; of infinite power, wisdom, and goodness, the Maker and Preserver of all things both visible and invisible. And in unity of his God-head there be three persons, of one substance, power and eternity, the Father, the Son, and the Holy Ghost.
The king was Edward VI, in what proved to be the final year of his reign.
Update: A look at early matches for 'Trinite' and an earliest match for 'holy Trinite'
In hopes of finding an earlier instance of "Holy Trinity," I ran a Google Books search for Trinite, the predecessor word in Middle English to Trinity. The most interesting result was a concordance to the A, B, and C versions of William Langland, William's Vision of Piers Ploughman, the famous medieval allegorical poem, which Wikipedia reports was written circa 1370–1390.
The concordance turns up several dozen matches for Trinite [or trinite], and it finds even more matches for holy (particularly in the combinations holy chirche [or churche or kyrke or kirke], holy gost [or goste or goost], and holy writ, but also occasionally in the forms holy day [or dayes or daies], holy men, and (once each) holy Seintes and holy euen. But there is only is only one instance in which holy and Trinite appear in the same line, and in that case holy modifies goost:
So grace of þe holy goost þe grete myȝl of þe Trinite
Virtually all instances of Trinite in Piers Ploughman are preceded by þe. This proves nothing about whether some contemporaries of William Langland used the term holy Trinite; but it does provide fairly strong evidence that in the late 1300s holy Trinite was not a set phrase in Langland's part of England the way that holy chirche, holy gost, and holy writ were.
In Tarjei Park, "Reflecting Christ: The Role of the Flesh in Walter Hilton and Julian of Norwich," in The Medieval Mystical Tradition in England: Exeter Symposium V (1992), the academic author reproduces several quotations from Julian of Norwich's Revelations of Divine Love (ca. 1395), including one that comes close to "holy Trinity":
For the Trinite is God, God is the Trinite; the Trinite is our maker and keeper, the Trinite is our everlasting lover, everlasting ioy and blisse, be our lord Iesus Christ. And this was sewed in the first and in all; for where Iesus appereith the blissid Trinite is understood, as to my sight.
Most of Julian's mentions of Trinite are unmodified, but the last one, blissid Trinite, comes close to holy Trinite. Still her choice of blissid in place of holy as the adjective suggests that "holy Trinite" was not a set phrase in her own mind.
An 1841 edition of Lyttleton, His Treatise of Tenures, in French and English includes in its introduction the text of Thomas Lyttleton's will (written not later than 1481), which includes this provision:
Also I bequeth my gode littel mass book and gode vestment with the apparel to an auter of the same sorte of vestments which were my moder's, and also a gilt chalës, I geve them to the blessed Trinitë, to the use and occupation of my chapel of Frankley in honour of our said most blessyd Trinitë: inasmuch as the said chapel of the blessyd Trinitë and an aulter thereof is halowed in the worship of the said blessyd Trinitë, for to have masse songen there on Trinitë Sunday and other high festivals and other days to the pleasure and honour of our said most blessyd Trinitë.
This is Julian of Norwich's preferred phrase with a vengeance (especially as Lyttleton charges that the Lord of Frankley must meet the terms of this bequest and obligation "as he will answer to the blessed Trinitë").
However, a search of the Early English Text Society's collection, Songs, Carols, and Other Miscellaneous Poems, from the Balliol Ms. 354, Richard Hill's Commonplace-book (1907), whose contents Hill gradually collected over the period 1508–1536, finds one crucial match. Searches within the book yield 43 pages matches for holy and 12 pages with matches for Trinite [or trinite or Trynite]—and one pair is in combination:
Vnto the Trinite.
Holy Trynite, blessed & eterne,
Ever regnyng in parfight vnite,
Whose power, Lord, no thynk may deserne,
Ne þe joyes nombre of thy dignite,
Thy grace euer in eche necessite
Be my ocowr, my fawtis to redresse,
& with thyn hond, Lord, euery day me blesse!
Google Books is very poor and finding matches from before the late 1500s, owing to the relative scarcity of early books in its database and to OCR problems with early English fonts. So there are surely some and perhaps many earlier instances of Holy Trinity in published English than the earliest one it finds (from no later than 1536). But there is at least some reason to doubt that Holy Trinity was already in widespread use in England as holy Trinite in the late medieval period, as well as some reason to suppose that during the period 1390–1490 the wording blessed [or blissid] Trinite may have been in more common use.