The continually growing level of debt in the vast majority of countries worldwide and the resulting significant increase in servicing costs is a major challenge for sovereign debt managers. This paper is part of research on the consequences of a permanent budget imbalance in non-eurozone new European Union member states in Central and Eastern Europe (CEE). The main objective is to investigate what determinants are ultimately associated with changes in the level of debt service costs among the countries selected for the analysis: Poland, the Czech Republic, Hungary, and Romania. Special attention is paid to the impact of credit ratings, which are a key uncertainty indicator that investors take into account when acquiring Treasury securities issued by indebted countries. The study covers the 2005–2017 period, a time frame that includes the latest global financial crisis, which led to a significant increase in spreads on Treasury bonds issued by the studied countries. The empirical part of the paper uses the panel dynamic ordinary least squares method (DOLS). The analysis identifies following determinants of debt servicing costs for selected CEE countries: rating agency reports, the level of volatility implied in the market, the budget deficit, the exchange rate, the debt level, and economic growth. The obtained results carry implications for public debt management policy.