Nowadays there is an increase of imported natural building stones, often used as replacement of local, more traditional building stones. The durability of these traditional stones is generally well known; however, when new imported materials are used, it is essential to study their behaviour under the current and local climatological conditions to predict their weathering resistance. In addition to water exposure, these building materials have to be resistant to significant mechanical stress created by the imbibition of de-icing salt solutions, frequently used during winter in Western Europe, with temperature periodically changing from freeze to thaw conditions. Porous network modifications related to the materials’ chemical composition are very complex when different forces are acting on the stone itself. Therefore it is crucial to determine the internal structure of the building stone under changing external conditions with and without the presence of de-icing salts, to understand the influence of these additional salts. In this paper, particular attention was paid to the multi-characterization of compact Kandla Grey laminated sandstone, a building stone frequently imported from India to Belgium recently. Traditional as well as highly advanced research techniques were used for the characterization and monitoring of changes under different external conditions. This study demonstrates that the structural characteristics of the laminations have an effect on the frost resistance of the stone and its response to salt weathering. From the experiments carried out, it can be concluded that Kandla Grey can be sensitive to frost and salt weathering under the current climatic conditions in Western Europe.