A study was conducted to explore the physicochemical and sensory quality of frozen skipjack (Katsuwonuspelamis), bigeye (Thunnusobesus), yellowfin (Thunnusalbacares), and kawakawa (Euthynnusaffinis) tuna fish fillets marketed in Tanga and Mtwara, Tanzania. The present study used the usual physicochemical and sensory properties to evaluate the quality of tuna-tuna and related fish species fillets. This study employed laboratory validated and standard (AOAC) methods to evaluate pH, color lightness properties (L*), and texture (hardness) of the fillets. Total volatile basic-nitrogen (TVB-N) was also estimated using a validated method that complied with guidelines number 95/149/EC issued by the Official Journal of the European Communities. Sensory evaluation was conducted using a designed quality index approach to assess color, texture (hardness), and odor. The results of the evaluation of tuna and tuna-related fish fillets were; pH 5.60±0.08 to 6.10±0.30, TVB-N 34.0±7 to 38.04±10.50 mg/100 g, color lightness properties (L*) 24.33±1.80 to 40.1±1.50, , and texture (hardness) 3.84±1.20 N to 8.60±1.84 N. Sensory evaluation of the tuna fillets gave an overall score of 2, which is medium quality.. Furthermore, the present study showed statistically significant differences (p<0.05) between the tuna species in pH, instrumental texture (hardness), and color lightness properties (L*). There were no statistically significant differences (p <0.05) in average TVB-N results across all tuna fillets. Significant weak, moderate, and strong negative and positive correlations (p < 0.01) were observed between the tuna and the tuna-related fish properties evaluated. In addition, market samples were better in quality than fish landing site samples. Based on the physicochemical and sensory properties reported in this study, the correlation between these properties, and the results of other studies, the evaluated tuna and tuna-related fish species sold in Tanga and Mtwara were of marginal (medium) quality.