The club was formed in 1911 and was the second team to be founded in Accra after the Invincibles. They are the oldest existing club in Ghana. The club was, in the most part, trained by Ackom Duncan, who would also become the team's first captain. Other members of the fledgling club were J.T. Ankrah (father of Ghana boxing great, Roy Ankrah), and C.B. Nettey, who was later to become the chairman of the Ghana Football Association.
Hearts of Oak won their first major match in 1922 when Sir Gordon Guggisberg, governor of the Gold Coast, founded the Accra Football League. Hearts won 6 out of 12 seasons in this league. In 1956, Hearts joined the Ghanaian football league and have flourished since.
Hearts suffered a great tragedy on 9 May 2001 when 126 people died in Africa's worst footballing disaster while watching a match between Hearts of Oak and Asante Kotoko. Trouble started when supporters of Asante Kotoko began ripping out seats in an act of hooliganism in protest at a goal allowed by the referee for Hearts of Oak, which they believe should have been disallowed for offside. Police reacted by firing tear gas into the crowd, it has been suggested that this was an over-reaction. Reports suggest that the gates to the ground were locked and that the rush to escape the tear gas was a contributory factor to the death toll. A commission inquiry did not indict the hooligans in its report.