Faits : A. Z._ SA est une société active dans le traitement et la récupération de papier et de tous déchets recyclables. Depuis le 1 er mai 2008, X._ travaillait en qualité d'ouvrier polyvalent à la succursale de... de cette entreprise. En février 2013, son salaire mensuel brut s'élevait à 4'150 fr. Le matin du 7 juin 2013, une altercation a eu lieu sur le lieu de travail entre X._ et son collègue A._. Ce dernier a notamment fait tomber X._ et lui a donné des coups alors qu'il se trouvait à terre. Selon deux certificats médicaux établis les 7 et 27 juin 2013, X._ a subi une incapacité de travail totale jusqu'au 20 juin 2013. Après avoir entendu les deux travailleurs ainsi que deux autres employés ayant assisté à la scène, l'employeur a, le matin même, licencié X._ et A._ avec effet immédiat pour des motifs identiques ainsi décrits dans les lettres de congé: " Aux environs de 7.30 h, vous avez eu une altercation violente avec un de vos collègues de travail, laquelle a dégénéré en bagarre avec agression physique et verbale. " Le 25 juin 2013, X._ a contesté la résiliation du contrat de travail avec effet immédiat, niant l'existence de justes motifs. L'employeur a refusé de revenir sur sa décision, soulignant qu'il ne pouvait en aucun cas tolérer la violence sur le lieu de travail. Le 11 juillet 2013, X._ a déposé une plainte pénale contre A._. Par ordonnance pénale du 11 mars 2014, ce dernier a été reconnu coupable de lésions corporelles simples au sens de l'art. 123 al. 1 CP et condamné à 40 jours-amende à 50 fr., peine assortie du sursis pendant deux ans. L'ordonnance pénale relate les faits suivants: " Le vendredi 7 juin 2013 vers 07h00, au sein de l'entreprise Z._ SA à..., le plaignant X._ et le prévenu A._, après s'être échangé quelques mots, se sont bousculés. A._ a alors poussé X._, qui est tombé à terre. Alors qu'il se trouvait au sol, le prévenu a encore donné des coups de pied et de poing dans les jambes, sur la poitrine, dans le dos et sur la tête du plaignant. X._ a subi une plaie de 0.5 cm de longueur superficielle temporale gauche, des douleurs à la palpation antérieure du gril costal et du muscle trapèze gauche, une tuméfaction antérieure tibiale de 5 x 10 cm sans rougeur, avec des douleurs locales à la palpation ainsi qu'une légère douleur du tibia, sans déformation ni tuméfaction. " Jusqu'au 30 juin 2014, X._ a perçu des indemnités journalières de la SUVA à hauteur de 80% de son salaire. B. Par demande du 25 novembre 2014, X._ a ouvert action contre Z._ SA en paiement de 4'131 fr.60 à titre d'indemnité pour les vacances non prises entre le 7 juin 2013 et le 28 février 2014, de prime annuelle et de salaire pendant les trois jours du délai d'attente de la SUVA, ainsi que de 17'983 fr.40 à titre d'indemnité pour licenciement immédiat injustifié. Il a par ailleurs conclu à la délivrance d'un certificat de travail; ce point fera l'objet d'une transaction devant l'autorité de première instance. Par jugement du 8 avril 2015, le Tribunal de prud'hommes de l'arrondissement de La Broye et du Nord vaudois a rejeté les conclusions en paiement du demandeur. X._ a interjeté appel. Par arrêt du 28 octobre 2015 dont les considérants ont été notifiés le 10 février 2016, la Cour d'appel civile du Tribunal cantonal vaudois a admis partiellement l'appel et réformé le jugement attaqué en ce sens que Z._ SA est condamnée à verser à X._ les montants de 602 fr.45 brut et 4'150 fr. net, le tout plus intérêts à 5% dès le 8 juin 2013. Contrairement au Tribunal de prud'hommes, la cour cantonale a reconnu le caractère injustifié du licenciement immédiat; elle a retenu que l'employeur n'avait pas démontré que le travailleur s'était battu avec A._, aucun élément ne laissant apparaître qu'il aurait porté des coups à son collègue. S'agissant des conséquences financières de la résiliation du contrat sans justes motifs, l'autorité précédente a fixé à 602 fr.45 le montant dû en indemnisation des vacances non prises jusqu'au 3 février 2014 et à 4'150 fr. - correspondant à un mois de salaire brut - l'indemnité due en vertu de l'art. 337c al. 3 CO. C. X._ interjette un recours en matière civile. Il conclut à la réforme de l'arrêt attaqué en ce sens que Z._ SA est condamnée à lui payer 652 fr.70 en indemnisation des vacances non prises et 17'983 fr.40 à titre d'indemnité allouée sur la base de l'art. 337c al. 3 CO, le tout plus intérêts. A titre subsidiaire, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité cantonale pour nouvelle instruction et nouveau jugement dans le sens des considérants. Par ordonnance du 18 août 2016, la cour de céans a admis la demande d'assistance judiciaire présentée par X._ et a désigné Me Vincent Demierre comme avocat d'office du recourant. Dans sa réponse, Z._ SA conclut au rejet du recours.