Najwcześniejsza wzmianka o Heart of Midlothian, w kontekście sportowym, pojawiła się w gazecie The Scotsman 20 lipca 1864. Artykuł dotyczył meczu krykieta pomiędzy Scotsman i Heart of Mid-Lothian. Nie jest znane czy był to ten sam klub, który w późniejszym czasie wszedł w skład grona założycieli Heart of Midlothian Football Club.
Hearts był jedynym klubem ze wschodniej Szkocji, który razem z kilkoma innymi drużynami z zachodniej części kraju założył Scottish Football League w 1890. To właśnie w początkowych latach działalności tych rozgrywek klub odnosił znaczące sukcesy, zdobywając mistrzostwo Szkocji w sezonie 1894/1895. Ponadto w 15-letnim okresie, od 1891 do 1906, klub czterokrotnie triumfował w Pucharze Szkocji – w latach: 1891, 1896, 1901 oraz 1906.
Za największy sukces klubu w tamtych czasach uważa się zwycięstwo w Pucharze Szkocji 14 marca 1896. W finale tych rozgrywek spotkały się dwie drużyny mające siedzibę w Edynburgu: Heart of Midlothian oraz Hibernian. Drużyna Hearts, w meczu rozegranym na Logie Green, w jedynym finale rozegranym poza Glasgow, pokonała lokalnego rywala 3:1. Jednym z najwybitniejszych piłkarzy, grających w bordowej koszulce był 29-krotny reprezentant Szkocji Bobby Walker.