The stress-dependent permeability of low-permeability sedimentary rocks has seized attention because of the growing need for fossil fuels, geological carbon sequestration, and radioactive waste disposal. The Kozeny-Carman equation (K-C equation) is a well-known model for predicting the permeability of sedimentary rocks. The Kozeny-Carman constant (K-C constant, ckc) in the K-C equation accounts for the shape of the pores and the complexity of the pore conduit geometry in rocks. The pore structure of rocks varies owing to compaction at different burial depths. Therefore, the ckc is stress-dependent, a key parameter for understanding the stress-dependent permeability of rocks. However, measuring the stress-dependent ckc in low-permeability rocks is challenging. The present study proposes a novel approach for measuring the stress-dependent ckc of low-permeability rocks. The key elements of the proposed approach are (1) utilizing the Klinkenberg slip factor to evaluate the pore structure of rocks under stress, and (2) measuring rock porosity and permeability simultaneously under stress. This study amended the existing apparatus to fulfill the aforementioned purpose. Silty sandstone and clayey siltstone were selected to illustrate the novel ckc measurement method. The measured ckc values were compatible with the measurement results of documented sandstones and mudstones (most stress-independent). Interestingly, the ckc increased with increasing effective confining stress but started to decrease when the applied stress exceeded a certain critical value. Finally, we provide a synthetic case demonstrating the importance of considering stress-dependent ckc for permeability prediction under stress. If we neglect the stress dependence of ckc, the prediction of permeability using the K-C equation can induce errors up to several orders of magnitude.