We present a detailed investigation of the magnetic and structural properties of magnetically doped 3D topological insulator Bi2Se3. From muon spin relaxation measurements in zero magnetic field, we find that even 5% Fe doping on the Bi site turns the full volume of the sample magnetic at temperatures as high as ~250 K. This is also confirmed by magnetization measurements. Two magnetic phases are identified; the first is observed between ~10-250 K while the second appears below ~10 K. These cannot be attributed to impurity phases in the samples. We discuss the nature and details of the observed magnetism and its dependence on doping level.