The interaction between interstitial solute atoms and screw dislocations was studied in several body centered cubic metals using electronic structure calculations based on the Density Functional Theory (DFT). In a first step, considering carbon solutes, we have evidenced a strongly attractive interaction in Fe, Mo and W, induced by a spontaneous reconstruction of the core structure towards a low energy configuration where, unexpectedly, the dislocation core adopts a hard-core configuration. The carbon atoms are at the center of regular trigonal prisms formed by the metal atoms in the dislocation core. The preference of carbon atoms for these prismatic sites can be related to the similarity with their local environment in Fe3C cementite and in WC and MoC hexagonal carbides. We have evidenced the same core reconstruction with other octahedral interstitial solutes (B, N, O) in Fe, whereas a totally different behavior is obtained for the carbon in V, Nb and Ta. We show, using a thermodynamic model, that this highly attractive interaction leads to complex segregation phenomena with a dislocation core fully saturated by solute atoms at low temperature even for very low bulk carbon concentrations. Finally, we investigated the consequences on the mobility of dislocations in Fe (C) based on the DFT calculations of the kink-pair formation and kink migration on decorated dislocations.