The cysteine protease legumain is involved in several biological and pathological processes, and the protease has been found over-expressed and associated with an invasive and metastatic phenotype in a number of solid tumors. Consequently, legumain has been proposed as a prognostic marker for certain cancers, and a potential therapeutic target. Nevertheless, details on how legumain advances malignant progression along with regulation of its proteolytic activity are unclear. In the present work, legumain expression was examined in colorectal cancer cell lines. Substantial differences in amounts of pro- and active legumain forms, along with distinct intracellular distribution patterns, were observed in HCT116 and SW620 cells and corresponding subcutaneous xenografts. Legumain is thought to be located and processed towards its active form primarily in the endo-lysosomes; however, the subcellular distribution remains largely unexplored. By analyzing subcellular fractions, a proteolytically active form of legumain was found in the nucleus of both cell lines, in addition to the canonical endo-lysosomal residency. In situ analyses of legumain expression and activity confirmed the endo-lysosomal and nuclear localizations in cultured cells and, importantly, also in sections from xenografts and biopsies from colorectal cancer patients. In the HCT116 and SW620 cell lines nuclear legumain was found to make up approximately 13% and 17% of the total legumain, respectively. In similarity with previous studies on nuclear variants of related cysteine proteases, legumain was shown to process histone H3.1. The discovery of nuclear localized legumain launches an entirely novel arena of legumain biology and functions in cancer.