Faits: A. X._, maître-boucher indépendant, a exploité, sous la forme d'une raison individuelle, la Boucherie X._, à .... Celle-ci a été transformée en société à responsabilité limitée en juin 2006. A partir du 1er janvier 1990, X._ a mandaté Z._ SA, succursale de ... (ci-après: la fiduciaire), pour qu'elle s'occupe de la comptabilité et de l'établissement de ses déclarations d'impôt. Depuis 1999, l'activité de la fiduciaire a consisté à entreprendre le bouclement annuel et à établir la déclaration fiscale. Les 5 et 6 avril 2005, l'Office d'impôt du District de Vevey a procédé à un contrôle fiscal périodique dans les locaux professionnels de X._, vérifiant à cette occasion ses bilans et ses comptes d'exploitation. Le 17 mai 2005, cet office a informé X._ que plusieurs irrégularités avaient été constatées dans la comptabilité. Le 30 juin 2005, l'Administration cantonale des impôts (ci-après: l'ACI) a adressé au contribuable, avec copie à la fiduciaire, un avis d'ouverture d'une procédure pour soustraction d'impôt portant sur la déclaration d'impôt 2003 et celles des années antérieures. Par courrier du 26 mai 2006, l'ACI a informé X._ - avec copie à sa fiduciaire - que ses investigations avaient permis d'établir qu'il n'avait pas comptabilisé l'intégralité de ses recettes et qu'il avait grevé son compte de résultat de charges non admises par l'usage commercial ou apparaissant contraires au droit fiscal. Elle lui a alors soumis une proposition de rectification de taxation par procédure simplifiée portant sur les déclarations d'impôts 2001, 2002 et 2003. Outre les modifications des déclarations d'impôt résultant de la reprise fiscale, ce courrier précisait ce qui suit: " (...) Nous attirons votre attention sur le fait que la présente proposition comprend une majoration des éléments rectifiés en lieu et place des amendes qui devraient être formellement prononcées. Si vous l'acceptez, la procédure d'enquête pour soustraction d'impôt sera clôturée par la présente décision de majoration laquelle vaut décision de sanction. Pour la bonne règle, vous voudrez bien, en cas d'accord, nous retourner le double des présentes, ci-joint, dûment daté et signé (...). " A la suite de cette proposition, la fiduciaire a interpellé l'ACI le 19 juin 2006, lui demandant de réintégrer un montant pour débiteurs plus important que celui apparaissant dans les comptes de X._. En réponse, l'ACI a adressé à ce dernier le 15 décembre 2006, une nouvelle proposition de rectification de taxation par procédure simplifiée tenant compte de l'erreur commise dans son précédent courrier. Le total général des compléments d'impôts cantonaux et fédéraux 2001-2003, y compris la majoration, dû par X._ a ainsi été arrêté à 271'112 fr. 30. Il ressort par ailleurs des décomptes détaillés de reprise joints à cette proposition que la majoration prononcée en lieu et place d'une amende a été fixée à 0,5 fois les éléments soustraits. X._ a accepté cette proposition de règlement et, le 5 mars 2007, il a adressé un courrier de réclamation à sa fiduciaire, lui réclamant le montant de 271'112 fr. 30, la tenant pour seule responsable de la soustraction d'impôt. La fiduciaire a transmis la réclamation à son assurance responsabilité civile qui, le 21 mai 2007, a indiqué à X._ qu'elle refusait d'entrer en matière sur la demande d'indemnisation aux motifs qu'il ne subissait aucun préjudice puisqu'il devait finalement s'acquitter d'un impôt dû et que son assurée n'avait commis aucune faute dans le cadre de son activité. Un échange de correspondance s'en est suivi entre le conseil de X._ et celui de la fiduciaire, sans qu'aucune solution transactionnelle ne puisse être trouvée. X._ a mandaté la société A._ SA pour déterminer le montant des majorations effectuées par l'ACI en lieu et place du prononcé d'une amende. Selon les calculs effectués par cette société, le total des majorations s'élève à 74'230 fr. 60. Suite aux renseignements fournis par l'autorité fiscale, la Caisse AVS de la Fédération patronale vaudoise (ci-après: la caisse AVS) a entrepris un réajustement de la cotisation personnelle de X._ et réclamé à celui-ci un montant de 5'261 fr. 80 à titre d'intérêts moratoires. Diverses factures établies par la fiduciaire n'ont pas été acquittées par X._. B. Par demande du 2 mai 2008 (dont les conclusions ont été amplifiées le 17 novembre 2008) adressée au Tribunal civil de l'arrondissement de La Côte, X._ a conclu à ce que la fiduciaire soit condamnée à lui payer la somme de 90'261 fr.80 correspondant au montant de 85'000 fr. (comprenant 74'230 fr.60 dus à titre de majoration fiscale, ainsi que d'autres postes secondaires qui ne sont plus discutés dans la procédure fédérale), plus 5'261 fr.80 (intérêts moratoires dus à la caisse AVS). La défenderesse a conclu au rejet de la demande et, reconventionnellement, à ce que X._ soit condamné à lui verser divers montants correspondants à des factures encore ouvertes. L'expert mandaté en cours d'instance a relevé que, selon les règles de l'art, diverses réserves n'auraient pas dû être constituées et que le risque de reprise fiscale en présence de telles réserves était élevé. L'expert a indiqué ne pas être en mesure de déterminer si l'attention de X._ avait été suffisamment attirée sur les conséquences et les risques inhérents à l'existence des réserves latentes et si c'était à la suite d'un conseil de sa fiduciaire qu'il avait accepté la procédure simplifiée de l'ACI. Des témoins ont été entendus lors de l'instruction. Par jugement du 3 février 2012, le Tribunal civil a condamné la défenderesse à verser au demandeur la somme de 74'230 fr. 60, plus la somme de 5'261 fr. 80 (ch. I du dispositif), sous déduction de deux montants (6'777 fr.60 et 1'335 fr.60) correspondant aux honoraires de la fiduciaire. La Cour d'appel civile du Tribunal cantonal vaudois, par arrêt du 10 juin 2013, a admis l'appel formé par la fiduciaire et, réformant le jugement de première instance (ch. I de son dispositif), rejeté la demande de X._. En substance, la cour cantonale a retenu que la majoration fiscale affligée au contribuable valait explicitement décision de sanction et qu'elle présupposait une faute de sa part, à tout le moins sous la forme d'une négligence. Elle en a conclu qu'en raison du caractère strictement personnel de l'amende prononcée, toute indemnisation (versée par un tiers) au contribuable était exclue. C. X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 10 juin 2013. Il conclut, sous suite de frais et dépens, à son admission et à la réforme de l'arrêt attaqué en ce sens que la fiduciaire lui doit le montant de 74'230 fr. 60, plus la somme de 5'261 fr. 80, sous déduction des montants correspondant aux honoraires de la fiduciaire, subsidiairement, à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité précédente. L'intimée conclut au rejet du recours, sous suite de frais et dépens.