The self-assembly of colloidal particles using DNA linker molecules has led to novel colloidal materials. This article describes the development and characterization of a new class of colloidal structures based on the directed assembly of DNA-linked paramagnetic particles. A key obstacle to assembling these structures is understanding the fundamental chemistry and physics of the assembly processes. The stability of these cross-linked chain structures is the first step toward reliable assembly and thus important for its applications; however, chain stability has yet to be systematically studied. In this paper, we investigate both theoretically and experimentally, the stability of DNA-linked paramagnetic colloidal chains as a function of externally applied magnetic field strength and surface grafted DNA length and density. A total interparticle free energy potential model is developed accounting for all major forces contributing to chain stability, and a phase diagram is obtained from experiments to illustrate linked chain phases, unstable unlinked particle phases, and their transitions, which agree well with those predicted by the model. From this study, optimized parameters for successful linking and building stable linked chains are obtained.