Common bean variety selection within its production environment is often challenged by the occurrence of significant genotype-by-environment interactions (GEI) in the variety development process. Grain yield performance of 16 navy bean (Phaseolus vulgaris L.) lines was tested in a multi-environment variety trial during 2010 and 2011 main growing seasons of Ethiopia. Field experiments were conducted in Randomized Complete Block Design (RCBD) with three replications in 14 rainfed environments of the major common bean growing areas. The objectives were to assess the line by environment interactions (LEI), determine stable genotypes, and grouping of test environments. Significant differences were found among the lines for grain yield on each environment and combined over environments. The combined analysis of variance across environments indicated that both environment and LE interactions were significantly influenced lines yield. All interactions in relation to L×E showed high significant difference (P<0.01) for grain yield. Statistical methods as AMMI, GGE and some stability parameters were used to describe the LE interaction and to define stable lines in relation to their yield. The highest yield (2435 kg ha-1) was obtained from the line ICA BUNSI X SXB 405/1C-C1-1C-87. The stability analysis also identified lines ICA BUNSI X SXB 405/1C-C1-1C-87 and ICA BUNSI X SXB 405/1C-C1-1C- 37 as the most stable lines. Lines identified as superior differed significantly from the standard varieties and can be recommended for use by farmers in the bean growing areas of Ethiopia. Cluster analysis, based on grouping of locations showed that Melkassa, Alemtena and Haramaya as potential and high yielding, but Jimma, Bako, Pawe, Areka, Assosa and Sirinka as low to medium yielding locations.