Il club fu costituito l'11 novembre 1911 ad Accra, capitale del Ghana. Vinse il primo titolo nel 1922, quando si tenne la prima edizione della Accra Football League, il torneo fondato dal governatore della Costa d'Oro (Gold Coast), Gordon Guggisberg. Delle 12 Accra Football League disputate, gli Hearts of Oak se ne aggiudicarono 6. Il club vinse anche la Gold Coast Club Competition, il torneo precursore coloniale della Premier League ghanese. Nel 1956 l'Hearts si unì alla Federazione calcistica del Ghana.
Il 9 maggio 2001, nel peggior disastro calcistico della storia dell'Africa, morirono 127 persone, durante la partita tra Hearts of Oak e Asante Kotoko. I problemi iniziarono quando i tifosi dell'Asante cominciarono a strappare i seggiolini in segno di vandalica protesta, quando l'Hearts conduceva per 2-1. La polizia reagì lanciando gas lacrimogeni fra la folla e questa venne ritenuta una reazione eccessiva.