Sachverhalt: A. X._ fuhr am 19. November 2013 gegen 7:15 Uhr auf der A8 in Richtung Interlaken. Um einen vor ihm auf der einspurigen und richtungsgetrennten Autostrasse fahrenden Personenwagen zu überholen, fuhr er auf den Rastplatz Därligen. Bei der Ausfahrt des Rastplatzes verlor er die Kontrolle über sein Fahrzeug und schleuderte quer über die Autostrasse. Dabei durchbrach er die Mittelleitplanke und kam auf der Gegenfahrbahn zum Stillstand. A._, der zu diesem Zeitpunkt dort fuhr, konnte eine Kollision nicht mehr vermeiden. Das Regionalgericht Oberland erklärte X._ deswegen am 11. März 2015 der groben Verletzung der Verkehrsregeln schuldig. Dagegen erhoben sowohl X._ als auch die Staatsanwaltschaft Berufung. B. Das Obergericht des Kantons Bern erklärte X._ am 23. Februar 2016 neben anderen Delikten der qualifizierten groben Verkehrsregelverletzung (Art. 90 Abs. 3 SVG) schuldig. Es bestrafte ihn dafür mit einer bedingten Freiheitsstrafe von 14 Monaten. C. X._ führt Beschwerde in Strafsachen. Er beantragt, er sei vom Vorwurf der qualifizierten groben Verkehrsregelverletzung freizusprechen. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen; subeventualiter sei er wegen grober Verkehrsregelverletzung schuldig zu sprechen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung. Der Beschwerde sei die aufschiebende Wirkung zu erteilen. D. Die Generalstaatsanwaltschaft und das Obergericht des Kantons Bern beantragen, die Beschwerde sei abzuweisen.