In real life situations, there are many issues in which we face uncertainties, vagueness, complexities and unpredictability. Neutrosophic sets are a mathematical tool to address some issues which cannot be met using the existing methods. Neutrosophic soft matrices play a crucial role in handling indeterminant and inconsistent information during decision making process. The main focus of this article is to discuss the concept of neutrosophic sets, neutrosophic soft sets and neutrosophic soft matrices theory which are very useful and applicable in various situations involving uncertainties and imprecisions. Thereafter our intention is to find a new method for constructing a decision matrix using neutrosophic soft matrices as an application of the theory. A neutrosophic soft matrix based algorithm is considered to solve some problems in the diagnosis of a disease from the occurrence of various symptoms in patients. This article deals with patient-symptoms and symptoms-disease neutrosophic soft matrices. To come to a decision, a score matrix is defined where multiplication based on max-min operation and complementation of neutrosophic soft matrices are taken into considerations.