Заснований в 1914 році клуб протягом перших років свого існування перебував у тіні міських грандів: «Граджянски», ХАШК і «Конкордії». Найбільш успішним же етапом історії можна вважати післявоєнні роки, коли команда протягом восьми сезонів (1947—1955) грала в Першій лізі Югославії. Кращий результат — третє місце (після «Хайдука» та «Црвени Звезди») в 1952 році. В 1957-м «Локомотива» знову покинула елітний дивізіон і до розпаду СФРЮ на вищому рівні не виступала.
В часи формування незалежного хорватського футболу футболісти «Локомотиви» брали участь в розіграшах нижчих ліг, переважно Третьої. Після вильоту у Четверту лігу в 2006 році, команда стала фарм-клубомзагребського«Динамо». Подібне співробітництво позитивно позначилося на виступах недавнього аутсайдера: сезон 2009/10 футболісти почали вже у Першій лізі. Щоб відповідати вимогам турніру, команда стала проводити домашні матчі на арені «Динамо» — «Максимирі».
У сезоні 2012/13, клуб виграв вперше медалі в історії, за кілька турів до кінця достроково забезпечив себе срібними медалями. У сезоні 2016/17 вперше вийшов до 3 кваліфікаційного раунду Ліги Європи, переграв послідовно УЕ «Санта-Колому» та РоПС та вийшов на «Ворсклу».