Eastern European countries have experienced many political upheavals and economic reforms since their declaration of independence of the U.S.S.R. Our study is intended for a series of estimations concerning the market structure of the banking in the Eastern European countries. Besides, we also attempt to assess the transformation of the competitive conditions of the banking industries in these countries. We employ three different methods for the assessment: The Panzar-Rosse Model, the Lerner index and the structural indicators (Concentration Ratio and HHI). We also use quantile regression to estimate the change of the H statistics corresponding to different deciles of the bank revenues beside the standard regression. The estimation results of the H statistics and the Lerner indice both indicate the banking markets of the Eastern European countries are characterized as monopolistic competition. Profitable banks in some countries face keener competition in the market. Besides, the Lerner index is affected by some variables, and tends to show the consistent estimation results with the H statistic in general. On the other hand, the structural indicators reveal a descending concentration in most Eastern European countries. However, the comparison between structural and non-structural methods does not support the general view that concentration undermines competition.