Abstract In this paper, we have firstly redefined the notion of neutrosophic soft set and its operations in a new way to handle the indeterminate information and inconsistent information which exists commonly in belief systems. Then, we defined neutrosophic soft matrix and their operators which are more functional to make theoretical studies and application in the neutrosophic soft set theory. The matrix is useful for storing a neutrosophic soft set in computer memory which are very useful and applicable. We finally construct a decision making method, called NSM-decision making, based on the neutrosophic soft sets.