Heathcote joined the British Royal Navy on 19 December 1828, becoming Lieutenant twelve years later, the position which he maintained on the Cowlitz. In 1849, he became a Commander and was then serving on the Constance.
In 1851, Heathcote petitioned for divorce from his wife Elizabeth Lucy Heathcote. She had born an illegitimate child in Newfoundland with one George Francis Law, Elizabeth’s brother, whom she claimed she had not seen since she was seven years old until he returned from India in 1848. She was consequently sent to Australia as a convict, leaving her boys behind, with the intent to remediate her sins by pursuing a religious life. Ironically, a descendent of Heathcote claims that his own ancestry is the result of illegitimate relations between Edmund and a lady named Emma, whom the captain would have known before marrying Elizabeth.