First-principles calculations on stoichiometric MonS2n and WnS2n(n=1-8) clusters show that their lowest energy atomic structures are dominated by a central core of metal atoms while the S atoms cap this core. We discuss in detail terminal, edge and face capping of tetrahedral and octahedral Mo clusters by sulfur atoms for off-stoichiometric compositions also. Capping on the terminal sites is found to be least favorable. Edge capped Mo4S6 and face capped Mo6S8 clusters have high symmetries and high stability among all the clusters we have studied. We find that magnetic isomers are lowest in energy for some clusters though bulk MS2 (M=Mo and W) is nonmagnetic. Our results on Mo6S8+p(p=0-6) clusters further show that Mo6S12 is magic with 4$\mu$B magnetic moment. The origin of magnetism and bonding nature in these clusters is discussed. Our finding could lead to the possibility of magnetic clusters of a variety of nonmagnetic transition-metal compounds and their interesting assemblies. {\textcopyright} 2005 The American Physical Society.