Faits : A. X._ a fait l'objet d'une dénonciation pour avoir, le 14 janvier 2015, conduit un véhicule automobile en dépit d'une mesure de retrait du permis de conduire et pour ne pas avoir annoncé un changement de direction. Le 10 février 2015, A._ a porté plainte contre X._. Selon la plainte, ce dernier aurait ce jour-là demandé à son amie, B._, de téléphoner à l'employeur d'A._, pour lui demander qu'il la menace de licenciement si elle ne retirait pas les plaintes qu'elle avait précédemment déposées contre lui. B._ aurait ajouté que X._ désirait la tuer. De plus, A._ a accusé X._ de l'avoir traitée de « connasse » à deux reprises lors d'une audience devant le Tribunal de l'arrondissement de l'Est vaudois. Elle a également expliqué qu'en 2013, X._ aurait déambulé sous sa fenêtre avec une carabine et qu'il la terrorisait. Par ordonnance pénale du 5 novembre 2015, rectifiée le 11 novembre suivant, le procureur a reconnu X._ coupable d'injure, de violation simple des règles de la circulation routière et de conduite d'un véhicule malgré un retrait du permis de conduire. Il l'a condamné à 30 jours-amende à 30 fr. le jour, à 360 heures de travail d'intérêt général et à 100 fr. d'amende, convertible en cas de non-paiement fautif en une peine privative de liberté de substitution d'un jour. Il a mis les frais de la procédure à la charge de X._. Cette ordonnance n'a pas été contestée. Par ordonnance du même jour, le procureur a classé la procédure pénale dirigée contre X._ pour menaces, a refusé le versement d'une indemnité au sens de l'art. 429 CPP et a laissé les frais à la charge de l'Etat. Il a considéré que X._ était hors de cause, dès lors qu'il n'était pas l'instigateur de l'appel de B._ à l'employeur de la partie plaignante. En revanche, il a retenu qu'il n'y avait pas lieu à l'allocation d'une indemnité en raison d'une part de l'absence de difficulté de la cause et d'autre part, parce qu'il ne s'agissait que d'un classement partiel. B. X._, par l'intermédiaire de son mandataire, a recouru contre l'ordonnance de classement, en particulier contre le refus d'une indemnité de 3'275 fr. 65 pour ses frais de défense en application de l'art. 429 CPP. Par arrêt du 25 janvier 2016, la Chambre des recours pénale du Tribunal cantonal vaudois a rejeté le recours et a mis les frais de la procédure à la charge de X._. C. X._ interjette un recours en matière pénale auprès du Tribunal fédéral. Il conclut, avec suite de frais et dépens, principalement, à la réformation de l'arrêt du 25 janvier 2016 en ce sens qu'une indemnité de 3'275 fr. 65 lui est allouée. Subsidiairement, il demande le renvoi du dossier au ministère public pour nouvelle décision. X._ sollicite par ailleurs l'assistance judiciaire.