Sachverhalt: A. H._ war seit 1995 in der Logistikbasis der Armee (LBA) angestellt. Nachdem diese von bestimmten Vorgängen Kenntnis erhalten hatte, kündigte sie mit Verfügung vom 16. Juli 2012 das Arbeitsverhältnis fristlos. Auf Einsprache hin bestätigte das Eidgenössische Departement für Verteidigung, Bevölkerungsschutz und Sport VBS mit Entscheid vom 5. Februar 2013 die Verfügung. B. Eine dagegen erhobene Beschwerde hiess das Bundesverwaltungsgericht mit Entscheid vom 5. Juni 2013 gut. Es stellte dabei in Aufhebung des Einspracheentscheids die Nichtigkeit der Kündigung fest. Gleichzeitig wies es die LBA an, H._ weiterzubeschäftigen. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt das VBS die Aufhebung des Bundesverwaltungsgerichtsentscheids. H._ lässt auf Abweisung der Beschwerde schliessen, soweit darauf einzutreten sei.