Faits: A. A.X._, ressortissant algérien né en 1965, est arrivé en Suisse le 2 avril 2002. Il a déposé une demande d'asile qui lui a été refusée par décision du 13 août 2002 de l'Office fédéral des réfugiés. Cette décision a été confirmée sur recours par la Commission de recours en matière d'asile. Un délai de départ a été fixé à A.X._ au 21 mai 2003. L'intéressé a été condamné à plusieurs reprises pour diverses infractions pénales aux peines suivantes: - cinq jours d'emprisonnement avec sursis durant deux ans pour appropriation illégitime, utilisation frauduleuse d'un ordinateur et défaut d'avis en cas de trouvaille (ordonnance pénale du 10 juin 2002 du Ministère public du canton de Neuchâtel); - cinq jours d'arrêt avec sursis pendant un an pour vol d'importance mineur (ordonnance pénale du 21 juin 2002 du Ministère public du canton ce Neuchâtel); - douze mois d'emprisonnement pour vols, recel et défaut d'avis en cas de trouvaille (jugement du 24 janvier 2006 du Bezirkgericht Zurich); - trois mois d'emprisonnement pour infraction aux dispositions sur le séjour des étrangers et expulsion du territoire suisse pour une durée de trois ans en raison de désobéissance à la police (jugement du 26 septembre 2006 du Tribunal de police du district de La Chaux-de-Fonds); - 440 heures de travail d'intérêt général, sous déduction de 21 jours de détention avant jugement pour vol, vol d'importance mineure, dénonciation calomnieuse et infraction aux dispositions sur le séjour des étrangers (jugement du 26 janvier 2009 du Tribunal correctionnel de l'arrondissement de l'Est vaudois et arrêt du 6 juillet 2009 de la Cour de cassation pénale); - 480 heures de travail d'intérêt général pour vol, violation graves des règles de la circulation routière et séjour illégal (jugement du 28 septembre 2009 du Tribunal de police du district de Neuchâtel). Le 25 août 2008, A.X._ a épousé, à Boudry, B._, détentrice d'une autorisation d'établissement. Il a demandé l'octroi d'une autorisation de séjour par regroupement familial. Par la suite, A.X._ a fait l'objet de plusieurs rapports de police pour vols. B. Par décision du 11 février 2009, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a rejeté la demande d'autorisation de séjour au motif que A.X._ avait été condamné à plusieurs reprises essentiellement pour vol. Cette décision a été assortie de l'obligation de quitter le territoire neuchâtelois sans délai. Le 13 mars 2009, les époux ont interjeté recours contre la décision du Service des migrations devant le Département de l'économie du canton de Neuchâtel (ci-après: le Département de l'économie). Ils estimaient qu'il n'avait pas suffisamment été tenu compte de la grave maladie dont souffrait l'épouse. Le Département de l'économie a rendu une ordonnance le 15 mai 2009 rejetant la requête de mesures provisionnelles. Cette décision a été confirmée par le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) et le Tribunal fédéral (arrêt 2C_483/2009 du 18 septembre 2009). Par décision du 8 mars 2010, le Département de l'économie a rejeté le recours des intéressés. Il a retenu que A.X._ avait été condamné à un total d'un peu plus de quinze mois d'emprisonnement. Cette peine, bien qu'inférieure aux deux ans fixés par la jurisprudence en relation avec l'art. 8 CEDH, était le résultat d'une multitude d'infractions perpétrées dans différents cantons sur une durée de sept ans. En récidivant régulièrement, l'intéressé avait démontré ne faire aucun cas ni des avertissements de l'autorité ni du respect de la sécurité et de l'ordre publics suisses. Le Département de l'économie a également indiqué que l'épouse était parfaitement au courant de la situation de son époux et qu'elle devait être consciente du risque important qu'une autorisation de séjour lui soit refusée. Elle était déjà malade au moment où elle l'avait épousé et avait pu vivre, entre ses deux mariages, sans la présence d'un époux. Sa maladie s'était peut-être aggravée, mais cet élément n'était pas suffisant pour faire pencher la balance du côté des intérêts privés des intéressés au vu de tous les éléments du dossier. C. Par arrêt du 26 octobre 2010, le Tribunal administratif a rejeté le recours de A.X._ et B.X._. Il a retenu que le comportement de l'intéressé démontrait que celui-ci se moquait du respect de la sécurité et de l'ordre publics en Suisse. L'intérêt au maintien de cet ordre et à la prévention des infractions pénales prévalait sur l'intérêt privé de A.X._ à demeurer auprès de son épouse. D. A.X._ et B.X._ ont déposé un recours en matière de droit public et un recours constitutionnel subsidiaire auprès du Tribunal fédéral. Ils lui demandent, sous suite de frais et dépens, principalement, d'annuler l'arrêt du 26 octobre 2010 du Tribunal administratif et d'octroyer une autorisation de séjour à A.X._, subsidiairement, d'annuler ledit arrêt. Le Service des migrations, le Département de l'économie, le Tribunal administratif et l'Office fédéral des migrations ont conclu au rejet du recours. Les 22 février et 11 avril 2011, le Département de l'économie a fait parvenir des pièces au Tribunal fédéral. 