We study the bosonic matrix model obtained as the high-temperature limit of two-dimensional maximally supersymmetric SU(N) Yang-Mills theory. So far, no consensus about the order of the deconfinement transition in this theory has been reached and this hinders progress in understanding the nature of the black hole/black string topology change from the gauge/gravity duality perspective. On the one hand, previous works considered the deconfinement transition consistent with two transitions which are of second and third order. On the other hand, evidence for a first order transition was put forward more recently. We perform high-statistics lattice Monte Carlo simulations at large N and small lattice spacing to establish that the transition is really of first order. Our findings flag a warning that the required large-N and continuum limit might not have been reached in earlier publications, and that was the source of the discrepancy. Moreover, our detailed results confirm the existence of a new partially deconfined phase which describes non-uniform black strings via the gauge/gravity duality. This phase exhibits universal features already predicted in quantum field theory.