Gordon had fallen in love with Jane Bridges, a girl of 17 who was able to tell the story 60 years afterwards to his biographers. Gordon did not declare his love until he came to say good-bye to her before leaving for Australia on 7 August 1853. "With characteristic recklessness he offered to sacrifice the passage he had taken to Australia, and all his father's plans for giving him a fresh start in life, if she would tell him not to go, or promise to be his wife, or even give him some hope." This Miss Bridges could not do, though she liked the shy handsome boy and remembered him with affection to the end of a long life. It was the one romance of Gordon's life. That Gordon realized his conduct had fallen much below what it might have been can be seen in his poems ... "To my Sister", written three days before he left England, and "Early Adieux", evidently written about the same time.
Gordon was just over 20 years old when he arrived at Adelaide on 14 November 1853. He immediately obtained a position in the South Australian mounted police and was stationed at Mount Gambier and Penola. On 4 November 1855 he resigned from the force and took up horse-breaking in the south-eastern district of South Australia. The interest in horse-racing which he had shown as a youth in England was continued in Australia, and in a letter written in November 1854 he mentioned that he had a horse for the steeplechase at the next meeting. In 1857 he met the Rev. Julian Tenison Woods who lent him books and talked poetry with him. He then had the reputation of being "a good steady lad and a splendid horseman". In this year his father died and he also lost his mother about two years later. From her estate he received £6944-18-1 on 26 October 1861. He was making a reputation as a rider over hurdles, and several times either won or was placed in local hurdle races and steeplechases. On 20 October 1862 he married Margaret Park, then a girl of 17.