El equipo fue creado en 1997 sobre la historia de un club deportivo anterior, el Nõmme Spordiklubi Kalju, ubicado en el distrito de Nõmme al sur de Tallin.[3] La división de fútbol había sido creada en 1923 y se mantuvo en activo hasta la Segunda Guerra Mundial. Cinco décadas después, varios deportistas estonios lo refundaron como el Nõmme Kalju actual.[3]
La trayectoria del Kalju tuvo un largo camino por las divisiones inferiores, hasta que en los años 2000 el productor musical Kuno Tehva tomó las riendas.[4] Después de ascender a la Esiliiga, la entidad derrotó en 2007 al FC Kuressaare para promocionar a la Meistriliiga, máxima categoría nacional. En su debut en la élite recurrió a un técnico brasileño afincado en el país, Getúlio Fredo, que logró mantener el proyecto en la élite. Finalmente, su mayor éxito llegaría a las órdenes del estonio Igor Prins: precedido por un segundo puesto en 2011, el Nõmme Kalju se proclamó campeón de Liga en 2012.[5] Aquel equipo estaba formado por jugadores como Tarmo Neemelo, el japonés Hidetoshi Wakui y el italiano Damiano Quintieri.[6]
El Nõmme Kalju se ha mantenido desde entonces entre los clubes más potentes del fútbol estonio. Su último título ha sido la Copa de Estonia de 2015.[7]