We examine the existence of relativistic stars in f(T) modified gravity and explicitly construct several classes of static perfect fluid solutions. We derive the conservation equation from the complete f(T) gravity field equations and present the differences with its teleparallel counterpart. Firstly, we choose the tetrad field in the diagonal gauge and study the resulting field equations. Some exact solutions are explicitly constructed and it is noted that these solutions have to give a constant torsion scalar. Next, we choose a non diagonal tetrad field which results in field equations similar to those of general relativity. For specific models we are able to construct exact solutions of these field equations. Among those new classes of solutions, we find negative pressure solutions, and an interesting class of polynomial solutions.