Thermoelectric materials can generate electricity by harnessing the temperature gradient and lowering the temperature through applying electromotive force. Lead chalcogenides based materials, especially PbTe-based ones, have shown extremely high thermoelectric performance. PbSe has a similar crystal structure and band structure to PbTe. Compared with the commonly-used PbTe, PbSe possesses a high melting point and has an abundant reserve of Se, making it attractive to high temperature thermoelectric applications. It has been theoretically proposed that Mn-doping in lead chalcogenide should be able to lower the temperature of band degeneracy, and experimental evidences have been represented in Mn-PbTe. However, such an experimental study as well as the investigations of influences of Mn on microstructure, mechanical, electrical and thermal properties has not been conducted in Mn-PbSe. In this work, Pb0.98-xMnxNa0.02Se (0 x 0.12) materials are prepared by the melting-quenching techniques combined with rapid hot-press sintering. Effects of Mn doping on the microstructures, mechanical and thermoelectric properties of PbSe samples are systematically studied. The refined lattice parameters from X-ray powder diffraction patterns show that the solubility of Mn in the matrix is in a range from 0 to 0.04. The back-scattered electron images and elemental maps reveal that the MnSe-rich impurity phases exist in the PbSe matrix, which makes the PbSe-MnSe system a nano-composite system. Pb0.96Mn0.02Na0.02Se has also such microstructures, implying that the solubility of Mn should be below 0.02. Cubic-phase MnSe-rich precipitates have the sizes ranging from 50 nanometers to 1-5 micrometers. They are well dispersed in the PbSe-rich matrix, as round or layered microstructures. The mechanical properties of the nanocomposites can be determined by micro-hardness measurements. Interestingly, the average Vickers hardness values of the PbSe-MnSe nanocomposites are significantly improved, which are 16.6% and 51.6% harder respectively in x= 0.02 and 0.06 samples than those of pristine PbSe. Smaller Mn content can optimize the figure of merit ZT due to the band convergence and additional phonon scattering by precipitates, while higher Mn content has little influence on ZT because of the saturated Seebeck coefficient and anomalous increase in lattice thermal conductivity. As a result, the highest figure of merit is 0.52 at 712 K, which is achieved in the Pb0.96Mn0.02Na0.02Se sample. By further adjusting the Na content from 2% to 0.7%, the carrier concentration is optimized. Thus, the Seebeck coefficient and power factor become higher. A figure of merit of 0.65 is achieved at 710 K in the PbSe-MnSe nano-composite with a nominal composition of Pb0.973Mn0.02Na0.007Se. We suggest that further optimizing the electrical properties may achieve a higher thermoelectric performance in the PbSe-MnSe system.