In addition to reinforced concrete and steel buildings, a large part of the existing building stock in Europe is made of stone masonry. Prediction of the structural behavior requires the development of a systematic material characterization of the mechanical properties and structural details (units, arrangement, bonding, inter-connection). This study aims to analyze the mechanical and physical behavior of building stones in the historical city of Gjirokastër, Albania, known also as the Stone City. A thorough investigation of the regional stone quarries was performed, and the collected samples were cut into regular prismatic specimens for further analysis. The experimental campaign consisted of the determination of flexural strength and compressive strength, water absorption, porosity, specific gravity as well as structural analysis of the masonry material, using the MQI (Masonry Quality Index) method. The test results showed that there is a large scattering in the values of the mechanical and physical stone properties such as compressive strength varying from 20 to 115 MPa and flexural strength from 8 to 25 MPa. However, the analysis of the masonry material revealed a satisfactory structural performance, based on a frequent, systematic respect of the good construction practices (i.e., the rules of the art) in Gjirokastër.