Sachverhalt: A. An der Generalversammlung der X._ Holding SA (Beklagte, Beschwerdeführerin) vom 9. Juni 2010 wurden A._, B._ sowie C._ als Verwaltungsräte nicht wiedergewählt, und angestrebte Neuwahlen von Verwaltungsratsmitgliedern kamen nicht zustande. Nach dem Rücktritt von D._ aus dem Verwaltungsrat der Beklagten anlässlich der Sitzung vom 15. Juni 2010 setzte sich dieser bis zur ausserordentlichen Generalversammlung vom 6. September 2010 nur noch aus den kollektivzeichnungsberechtigten Verwaltungsräten E._ und F._ zusammen. An der Generalversammlung vom 6. September 2010, welche A._ mit Schreiben vom 13. Juni 2010 gestützt auf Art. 699 Abs. 3 OR verlangt hatte, wurden G._, H._, A._, I._, B._, J._ sowie C._ neu bzw. wieder in den Verwaltungsrat gewählt. Am 5. August 2010 erfolgte ein erster Kontakt zwischen Rechtsanwältin Z._, die für die Beklagte handelte, und Rechtsanwalt K._ von der Anwaltskanzlei Y._ Rechtsanwälte (Klägerin, Beschwerdegegnerin) betreffend auszuführender Arbeiten für die Beklagte. Mit Schreiben vom 9. September 2010 kündigte die Beklagte das allfällig bestehende Auftragsverhältnis mit der Klägerin mit sofortiger Wirkung. E._ und F._ wurden im Handelsregister am 9. März 2011 als kollektivzeichnungsberechtigte Verwaltungsräte der Beklagten gelöscht. B. B.a. Mit Klage vom 30. Mai 2011 beantragte die Klägerin dem Handelsgericht des Kantons Zürich, die Beklagte sei zu verpflichten, ihr Fr. 78'582.40 zuzüglich Zins zu 5 % seit dem 3. November 2010 zu bezahlen (Ziff. 1) und es sei in der Betreibung Nr. qqq des Betreibungsamts Nyon, Zahlungsbefehl vom 14. April 2011, der Rechtsvorschlag zu beseitigen und ihr für diesen Betrag die definitive Rechtsöffnung zu erteilen (Ziff. 2); unter Kosten- und Entschädigungsfolge zu Lasten der Beklagten (Ziff. 3). B.a.a. Die Klägerin führte zur Begründung ihrer Klage aus, A._ habe die Beklagte bis zu seiner Nichtwiederwahl praktisch ohne Einschränkungen geführt, weshalb es dem verbleibenden Verwaltungsrat nach seinem Ausscheiden ein Anliegen gewesen sei, die bestehenden, teilweise undurchsichtigen Geschäftsstrukturen der Beklagten von unabhängiger Seite durchleuchten zu lassen. Deshalb sei die L._ AG damit betraut worden, die frühere Unternehmensführung zu überprüfen und zu analysieren. Aufgrund der Erkenntnisse aus dem Bericht der L._ AG habe sich der Verwaltungsrat entschieden, das Verhalten der bisherigen Unternehmensführung, insbesondere jenes von A._, auch unter strafrechtlichen Aspekten überprüfen zu lassen, weshalb die Klägerin mandatiert worden sei. Die anwaltliche Tätigkeit habe insbesondere Rechtsberatung, Beurteilung strafrechtlicher Vorgänge, Ausarbeitung von Strafanzeige (n) sowie Unterstützung bei der Kommunikation und der Strategieführung umfasst. Es seien Leistungen im Wert von insgesamt Fr. 78'582.40 (inkl. MWST) erbracht worden. Das Stundenhonorar habe Fr. 500.-- betragen. B.a.b. Die Beklagte beantragte mit Klageantwort vom 14. Oktober 2011, die Klage sei abzuweisen und die Rechtsöffnung in der Betreibung Nr. qqq des Betreibungsamts Nyon sei zu verweigern. Sie machte im Wesentlichen geltend, nach dem Rücktritt D._ aus dem Verwaltungsrat sei das durch die Statuten und das Organisationsreglement der Beklagten vorgesehene Quorum von mindestens drei Verwaltungsräten nicht mehr erfüllt gewesen. Der Verwaltungsrat der Beklagten sei damit in der Zeit vom 15. Juni 2010 bis 6. September 2010 und somit während des von der Klägerin behaupteten Mandatsverhältnisses nicht mehr gehörig bestellt und beschlussfähig gewesen. Das Mandat mit der Klägerin sei deshalb nicht rechtsgültig zustande gekommen. Während der Zeit des "Putsches" sei die Geschäftsführung der Beklagten über das sogenannte "Kleine Komitee" erfolgt, dem u.a. E._, F._ und Rechtsanwältin Z._ angehört hätten. Sie bestritt die Honorarforderung auch im Quantitativen. Schliesslich sei das angebliche Mandat betreffend Strafanzeige nicht in ihrem Interesse gewesen, wie sich auch aus der Einstellungs- bzw. Nichtanhandnahmeverfügung des juge d'instruction du canton de vaud vom 10. November 2010 ergebe. B.b. Mit Beschluss und Urteil vom 12. Juli 2013 erkannte das Handelsgericht des Kantons Zürich, Ziffer 2 des klägerischen Rechtsbegehrens werde als durch Rückzug erledigt abgeschrieben und die Beklagte werde unter Kostenfolge verpflichtet, der Klägerin Fr. 78'582.40 zuzüglich Zins zu 5 % seit 13. November 2010 zu bezahlen. Im Mehrbetrag (Zins) wurde die Klage abgewiesen. C. Mit Beschwerde in Zivilsachen beantragt die Beklagte dem Bundesgericht, das Urteil des Handelsgerichts des Kantons Zürich vom 12. Juli 2013 sei aufzuheben und die Klage sei abzuweisen. Eventualiter sei die Sache zur Ergänzung des Sachverhalts und Neubeurteilung an die Vorinstanz zurückzuweisen. Die Klägerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. D. Mit Präsidialverfügung vom 10. Oktober 2013 wurde das Gesuch der Beschwerdeführerin um Gewährung der aufschiebenden Wirkung abgewiesen.