In the five-dimensional Einstein gravity with negative cosmological constant in the presence/absence of a {\it non-fine-tuned} 3-brane, we have investigated the classical stability of black string solutions which are foliations of four-dimensional $AdS/dS$-Schwarzschild black holes. Such black strings are generically unstable as in the well-known Gregory-Laflamme instability. For $AdS$ black strings, however, it turns out that they become stable if the longitudinal size of horizon is larger than the order of the $AdS_4$ radius. Even in the case of unstable black strings, the $AdS$ black strings have a very different feature of string fragmentations from that in the flat brane world. Some implications of our results on the Gubser-Mitra conjecture are also discussed.

13 pages, 3 figures, revtex, a comment on the work by Emparan, Horowitz, and Myers in one dimension less added