The Iranian banking system has faced a significant paradox in recent years regarding the relationship between costs and profitability. Empirical observations indicate that some banks have achieved satisfactory profitability despite high operational costs, while other banks have faced persistent losses with much lower costs. This research aims to analyze this puzzle using a quantile regression approach and data from 20 banks listed on the Tehran Stock Exchange during the period 2011-2023. The findings reveal that the relationship between costs and profitability is nonlinear and dependent on the bank's profitability level. Specifically, in loss-making banks (0.25 quantile), costs have a positive and significant effect on profitability, while this effect approaches zero in profitable banks (0.75 quantile). Additionally, the identification of an inverted U-shaped relationship between costs and profitability confirms the existence of an optimal point for banking costs. These findings highlight the necessity of adopting differentiated policies for banks based on their profitability levels and the need to revise general cost-reduction policies in the banking system.