  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.
