Damage localization approaches based on changes of flexibility constitute an important technique for damage detection. Construction of flexibility matrix with output-only data is still unfathomed, and this makes flexibility-based approaches not applicable in ambient vibration. An algorithm is presented to construct a Proportional Flexibility Matrix (PFM) from a set of arbitrarily-scaled modal shapes and modal frequencies. By scaling and redistributing the mass of real structure, a dummy structure is obtained. The ratios among the modal masses of the real and dummy structures can be deduced, and then the PFM is constructed. PFMs for the pre-damaged and post-damaged structure are employed to do damage localization by the Damage Locating Vector (DLV) method. To make the two flexibilities comparable, a normalization scheme of mass matrix is presented. A numerical example shows that a small number of measured modes can produce PFMs with sufficient accuracy to correctly locate the damage employing the DLV method.