Fremantle was the son of Admiral Thomas Fremantle, a close associate of Nelson, and his wife Elizabeth, the diarist, and a nephew of William Henry Fremantle. His elder brother was Thomas Fremantle, 1st Baron Cottesloe. His middle name, Howe, is a consequence of his birth date, the anniversary of Lord Howe’s victory over the French on the Glorious First of June in 1794. He joined the Royal Navy in 1812.
In 1824 he was awarded the first gallantry medal of the newly formed Royal National Institution for the Preservation of Life from Shipwreck, later the Royal National Lifeboat Institution. The gold medal was awarded for an attempted rescue carried out by Freemantle in Whitepit near Christchurch, Dorset.
According to Graeme Henderson, former director of the Western Australian Maritime Museum, Fremantle was charged with raping a 15-year-old girl in April 1826. To avoid a scandal, his family paid off witnesses and leant on the judiciary. In August 1826 he was promoted to captain, and, in 1828, given command of the 26-gun frigate HMS Challenger, and sent to claim the west coast of Australia for the United Kingdom.