Régi és tekintélyes köznemesi családból származott. Pesten született két évvel a '48-as forradalom előtt. Apja, Szekrényessy József Széchenyi István bizalmas munkatársa volt, Pest első közjegyzője, aki a szabadságharc bukása után sokak életét mentette meg. Ő bérelte Kálmán fia gyermekkorában a Rudas fürdőt, a Császár fürdőt, a Lóversenyteret. Az ő bérleményeiben tanult meg úszni Kálmán, akinek már tizenhat éves korában cikkei jelentek meg a kor legtekintélyesebb lapjában, a Pesti Naplóban.
Először orvosnak tanult, aztán jogásznak, a Zeneakadémiára is járt.
Húszéves korában önkéntesnek jelentkezett az osztrák hadseregbe, és részt vett a függetlenségért harcoló olasz seregek elleni csatában Custozzánál. Egy szúrt, két lőtt és három vágott sebbel élte túl a csatát. Szép kitüntetést kapott. Bennmaradt a hadseregben, elvégezte a hároméves osztrák kadétiskolát. Sokfelé szolgált. Hosszabb ideig Galíciában. 1870-ben részt vesz a francia-porosz háborúban a poroszok oldalán. Ott volt a sedani csatában és a párizsi bevonulásnál. Harcolt Spanyolországban Don Carlos trónkövetelő oldalán.