Transglutaminase (Tgase) crosslinking and calcium reduction were investigated as ways to improve the texture and storage stability of high-protein nutrition (HPN) bars formulated with milk protein concentrate (MPC) and micellar casein concentrate (MCC). The MPC and MCC crosslinked at none, low, and high levels, and a reduced-calcium MPC (RCMPC) were each formulated into model HPN bars. Hardness, crumbliness, moisture content, pH, color, and water activity of the HPN bars were measured during accelerated storage. The HPN bars prepared with MPC were harder and more cohesive than those prepared with MCC. Higher levels of Tgase crosslinking improved HPN bar cohesiveness and decreased hardening during storage. The RCMPC produced softer, yet crumblier HPN bars. Small textural differences were observed for the HPN bars formulated with the transglutaminase crosslinked proteins or RCMPC when compared with their respective controls. However, modification only slightly improved protein ingredient ability to slow hardening while balancing cohesion and likely requires further improvement for increased applicability in soft-texture HPN bars.