Faits : A. Par jugement du 24 septembre 2018, le Tribunal de police des Montagnes et du Val-de-Ruz a reconnu X._ coupable de violation simple de la LCR (art. 90 al. 1 LCR), dénonciation calomnieuse (art. 303 CP), conduite sans autorisation (art. 95 al. 1 LCR) et faux dans les certificats (art. 252 CP). Il a prononcé une peine privative de liberté ferme de six mois et renoncé à révoquer le sursis accordé le 27 septembre 2016. B. Par jugement du 13 mars 2019, la Cour pénale du Tribunal cantonal du canton de Neuchâtel a très partiellement admis l'appel formé contre ce jugement par X._ et déduit de la peine ferme confirmée un jour de détention avant jugement. C. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre le jugement du 13 mars 2019. Il sollicite, avec suite de frais et dépens, l'annulation des deux jugements précités, son acquittement du chef d'accusation de faux dans les certificats et sa condamnation à une peine pécuniaire d'au plus 135 jours-amende, assortie du sursis complet et sous déduction d'un jour de détention avant jugement. A titre subsidiaire, il conclut à l'annulation du jugement du 13 mars 2019 et au renvoi de la cause à l'autorité précédente pour nouvelle décision. Il requiert le bénéfice de l'assistance judiciaire. Invités à se déterminer sur le recours, l'autorité précédente y a renoncé, le ministère public a conclu à son rejet.