The Gordon name originated in France, from whence the name was brought by Anglo-Normans who settled in southern Scotland in the twelfth century. The first person recorded with the name was Richer de Gordun in the year 1150.
There is a place with the name Gordon, in the Merse, in Berwickshire, associated with the family.
Adam de Gordon, and Adam Gordon, received coats of arms from King Henry III for taking part in the crusade to Acre, in 1271-2, and later, another coat of arms was awarded to Sir Thomas Gordon.
In a survey in 1958, it was the 52nd commonest name in Scotland. 
The dukes of Richmond, and the marquess of Aberdeen, and the marquess of Huntly, are of the family name Gordon. The earlier clan leaders adopted peasants into their clan as vassals in return for food and protection, and as a result, large numbers bore the name as early as the second half of the fifteenth century.

Gordons in Ireland
The Gordon surname is recorded in Ireland in all provinces, although most common in Ulster. Most use the spelling Gordon, with a few instances of Gordan, Gorden and de Gordún. The earliest records are of mercenaries from the mid-fourteenth century.
The gaelic names MacMhuirneacháin, or MacGurnaghan, and Mórbhoirneach have become Gordon in some instances, especially in Connacht.
Hugh O'Neill, Earl of Tyrone, hired gallowglass soldiers from Scotland to fight the English in his Nine Years War. A force of gallowglasses was sent to assist the Irish Catholic cause, by George Gordon, the 5th Earl of Huntley, and his son, also George, the 6th Earl. The Earls supported Mary, Queen of Scots, and hoped to have the Catholic faith restored in Scotland and England. Some of these men would have had the Gordon surname, and they were Catholics. Most returned to Scotland after O'Neill was defeated at Kinsale in 1601, although some may have been in his employ until he surrendered in 1603.
It is possible that a few remained in Ireland.
There were Gordons who fought on the English side, and they were probably Protestants.
On 20th of April 1608, a few months after the Flight of the Earls, Sir Cahir O'Doherty of Inisowen rebelled, and attacked Derry, which was protected by two English forts. His men were unable to arm themselves properly, as all weapons had been confiscated.
An officer who was garrisoned in one of the forts during the surprise attack was a Lieutenant Gordon, who rushed out naked and killed two of O'Doherty's men, before he was himself killed, after he had been knocked unconscious with a stone.
In the Plantation of Ulster, Sir Robert Gordon had lands in county Donegal, which he bought from a planter in 1614. He bought another planter's portion in 1615, but the lands were confiscated sometime later, as he had failed to keep to the conditions of the plantation.
In 1832, when the Reform Act increased the number of voters to change the representation from that of 'property to the numerical force of the people', one of those who objected was James E Gordon, MP for Dundalk, who said he wished to stand up for the interests of Protestant ascendancy in Ireland. At the time, Dundalk had 32 persons eligible to vote out of a population of 10,750.

Gordons in Mayo
In 1796, three Gordons from Mayo applied for a grant, or bounty, for growing flax. They were:

Anthony in the parish of Crossmolina
Dominick in the parish of Kill
James in the parish of Turlough

A letter written on 17/07/1846 (Ref: RLFC3/1/ No: 4411) by George Crampton, secretary of the Belmullet Relief Committee, acknowledged notification of the appointment of Captain Gordon as inspecting officer of public works in Mayo and described the reappearance of blight in the new potato crop. There is no known connection between this officer and the family.

In 1856, there were 28 Gordon properties liable for rates in county Mayo:

1. Gordon, Anthony Crossmolina Tobermore ***************
2. Gordon, Anthony Kilgarvan Carrowcastle
3. Gordon, Bridget Aglish Town of Castlebar, New Antrim St.
4. Gordon, Bryan Kilbeagh Currinah
5. Gordon, Edward Breaghwy Drumcorrabaun
6. Gordon, Edward Breaghwy Keelkill
7. Gordon, Elizabeth Kilcolman Town of Ballaghaderreen, Longford Road
8. Gordon, James Ballysakeery Carrowkelly
9. Gordon, James Kilcolman Ballaghaderreen
10. Gordon, James Kilcolman Ballyoughter
11. Gordon, James Kilcolman Derrynacross
12. Gordon, John Kilmoremoy Town of Ballina, Durkin's Lane
13. Gordon, Martin Knock Bohaun
14. Gordon, Mary Addergoole Lahardaun
15. Gordon, Mary Kilmovee Aghadiffin
16. Gordon, Mary Kilmovee Culliagh
17. Gordon, Matthew Kilgeever Carrowmore
18. Gordon, Michael Kilcolman Ballaghadereen
19. Gordon, Michael Kilcolman Town of Ballaghaderreen, Pound St
20. Gordon, Michael Killasser Cuillonaghtan
21. Gordon, Parick Kilbeagh Currinah
22. Gordon, Patrick Crossboyne Seefin
23. Gordon, Sarah Kilmore Ballymacsherron (Widow)
24. Gordon, Thomas Kilbeagh Currinah
25. Gordon, Thomas Kilmovee Ranagissaun
26. Gordon, Thomas Jr Kilbeagh Currinah
27. Gordon, Timothy Kilmovee Magheraboy
28. Gordon, William Kilfian Knockaskeehaun

The earliest record for this family is of Anthony Gordon, born about 1800, who married Winnie Moran in 1830. He was probably descended from the Anthony Gordon who was paid the Flax Premium in 1796. 
There was a Michael Gordon, shoemaker, had a property in Crossmolina town in 1809.

1-- Anthony Gordon (born 1800) married Winnie Moran. His land was worth £6.0.0 at the time of the Tithe Applotment survey in 1830. He then moved from Ballyvicmaha to Tobermore sometime between 1830 and 1834, (where his holding was 8 acres) possibly to the holding of a James Moran, who may have been related to his wife. In 1850, his holding consisted of 15 acres, and a share in bogland of 14 acres. The widow was in possession in 1870, her name given as Mary? Presumably it is intended to read Winnie.
They had these children:
2-- Hugh Gordon (1832)
2-- Anthony Gordon (1836-1880) of whom more follows
2-- Patrick Gordon (1841)
2-- Michael Gordon married Ann McGowan; no other information
2-- Catherine Gordon married James Brogan on 14 February 1858 (she was known as Cate). Catherine (1851) and James (1846), if they are the same, lived in  Polladoohy, and they had these children, according to the 1901 census: John, 1867, Edward, 1871, James 1873 (the Registry of Births Marriages and Deaths has a record that James was born 2 March 1869), Mary, 1877. (The dates for the parents are wrong also.)

2-- Anthony Gordon was born in 1836, at Ballyvicmaha, Crossmolina, Co Mayo, and died at Tobermore in 1880 (this date may not be correct; see below, it should be at least 1886). He married Mary Murphy, of Tooreen, Crossmolina, Co Mayo. His wife was left with a family of young children when he died, according to the rental books of the landlord, Mervyn Pratt. His son John held the property by 1893, as a fifteen year old, so the mother must have died by then also. Anthony died when his son, John, was a child, with the result that information about the family and its origins was not passed on.
Anthony and Mary (Murphy) Gordon had the following children:
3-- Mary Gordon born 24 March 1875. She enrolled in Richmond NS in 1894 as Maria. She emigrated to the USA.
3-- Michael Gordon born 6 December 1877. This child had poor health, did not go to school, and died young. He was not included in the 1901 census.
3-- John Gordon born 1878, attended Richmond NS from 1894. He married Mary McGoff, daughter of Peter and Belinda (Mullen) McGoff, (in 1901, the McGoff household in Tobermore consisted of Peter, head of the household, aged 47 years, and born about 1854, a farmer, Belinda, his wife, aged 40 years, so born 1861, a son Peter, aged 10 years, Patrick aged 8 years, and daughters Mary, aged 6 years, and Ellen aged 4). Mary was born in Tubbermore in 1894, and died 23 March 1945, buried Kilmurry. John was a thatcher and farmer, according to the folklore essay collection in UCD. He had a particularly well-kept house and garden; a showpiece in the locality. The townland was called Gortduff, but that name seems to have become obsolete and it is now Polladuigh (or Pollahoohey). He made poitín and was prosecuted when he was caught. He died at River View, on 4 May 1970, and is buried at Kilmurry.
3-- Patrick Gordon born 11 March 1886; moved to live in the UK, possibly Scotland. We must assume that Anthony's death took place about the time of this son's birth. 

At the time of the 1901 census, the Tobermore household consisted of an aunt, Fanny Gordon aged 71 years, and single, so a sister of Anthony, presumably, and born about 1830; Mary the widow, aged 40, and therefore born in 1861, making her a very young bride, mother (at 14), and a widow (at 19!); and two sons, John aged 18, so born in 1883, and Pat aged 14, so born in 1887, both years after the date given for their father's death! The date of 1880 given for the death of Anthony must be considered incorrect. It is very likely to be a transcription error for 1886.