Sachverhalt:
A.
A._ meldete sich mit Hinweis auf Rückenbeschwerden erstmals im Jahr 1994 bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle des Kantons Bern wies das Gesuch mit Verfügung vom 10. April 1995 ab. Es folgten fünf weitere Anmeldungen, die allesamt abgewiesen wurden.
Nach erneutem Leistungsgesuch vom 7. November 2008 gewährte die IV-Stelle A._ eine Viertelsrente ab 1. Mai 2009 (Verfügung vom 27. April 2010). Im Juni 2011 beantragte er eine Rentenerhöhung, welche die Verwaltung mit Verfügung vom 29. September 2011 verneinte. Die dagegen von A._ geführte Beschwerde wies das Verwaltungsgericht des Kantons Bern mit Entscheid vom 4. Juni 2012 ab und hob die Rente nach angedrohter Schlechterstellung (reformatio in peius) auf.
Am 23. Februar 2015 stellte A._ ein neues Leistungsbegehren mit Verweis auf Berichte seines Hausarztes Dr. med. B._, FMH für Innere Medizin, vom 13. Dezember 2013 und des Spitals C._ vom 24. März 2014. Darauf trat die IV-Stelle nach durchgeführtem Vorbescheidverfahren nicht ein (Verfügung vom 13. Oktober 2015).
B.
Das Verwaltungsgericht des Kantons Bern wies die gegen die Nichteintretensverfügung erhobene Beschwerde von A._ mit Entscheid vom 21. März 2016 ab.
C.
A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt, unter Aufhebung des angefochtenen Entscheides sei die Sache zur Vervollständigung der Akten und zur Neubeurteilung an die IV-Stelle, eventuell an die Vorinstanz, zurückzuweisen.

Erwägungen:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>).
2.
Die für Verwaltung und Gericht geltenden Prüfungsobliegenheiten in Zusammenhang mit der Eintretensfrage bei Neuanmeldungen (Art. 87 Abs. 3 i.V.m. Abs. 2 IVV; <ref-ruling> E. 5.3.1 S. 112) hat die Vorinstanz zutreffend dargelegt. Darauf wird verwiesen.
3.
Streitig und zu prüfen ist, ob die Beschwerdegegnerin auf das Gesuch des Versicherten vom 23. Februar 2015 hätte eintreten müssen, was der angefochtene Entscheid verneint.
3.1. Das kantonale Gericht schützte das Nichteintreten mit der Begründung, der Beschwerdeführer habe eine anspruchserhebliche Änderung seines Gesundheitszustandes nicht glaubhaft und eine erwerbliche Veränderung nicht geltend gemacht. Die mit <ref-ruling> erfolgte Änderung der Rechtsprechung sei für sich allein kein Neuanmeldungsgrund.
3.2. Der Beschwerdeführer rügt in rechtlicher Hinsicht, das kantonale Gericht habe ihm in Verletzung von Treu und Glauben - überspitzt formalistisch - keine Frist zur Einreichung eines Arztberichtes bezüglich des erlittenen Herzinfarktes eingeräumt, obwohl er in seiner vorinstanzlichen Beschwerde einen entsprechenden Hausarztbericht als Beweismittel angeführt habe. Sinngemäss macht er weiter geltend, das kantonale Gericht habe zu Unrecht das Vorgehen der Beschwerdegegnerin geschützt, welche trotz hausärztlich bestätigter Verschlimmerung des Rücken- und Nackenleidens auf eine umfassende medizinische Untersuchung verzichtet und gestützt auf die Berichte des Regionalen Ärztlichen Dienstes (RAD) vom 14. April und 1. Oktober 2015 eine Verschlechterung verneint hatte.
4.
4.1. Ob das Beweismass des Glaubhaftmachens richtig angewandt wurde, prüft das Bundesgericht frei. Hingegen ist es an die vorinstanzliche Sachverhaltsfeststellung grundsätzlich gebunden (Art. 105 Abs. 1 und 2 BGG), anhand welcher die Rechtsfrage nach der Glaubhaftigkeit der geltend gemachten Änderung beantwortet wird (Urteil 9C_286/2009 vom 28. Mai 2009 E. 2.3, in: SZS 2009 S. 397).
4.2. Im Neuanmeldungsverfahren ist es in erster Linie Sache der versicherten Person, substanzielle Anhaltspunkte für eine allfällige neue Prüfung des Leistungsanspruchs darzulegen. Eine Pflicht der Verwaltung zur Nachforderung weiterer Angaben besteht nur, wenn den - für sich allein genommen nicht Glaubhaftigkeit begründenden - Arztberichten konkrete Hinweise entnommen werden können, wonach möglicherweise eine mit weiteren Erhebungen erstellbare rechtserhebliche Änderung vorliegt (vgl. das bereits zitierte Urteil 9C_286/2009 E. 2.2.3). Betreffend den vom Beschwerdeführer anfangs September 2014 erlittenen Herzinfarkt hat das kantonale Gericht mit zutreffender Begründung, auf die verwiesen werden kann (<ref-law>), erwogen, dass im Verwaltungsverfahren kein Anlass zu ergänzenden Abklärungen bestand. Erst Recht keine beweismässigen Weiterungen waren im vorinstanzlichen Verfahren angezeigt, in welchem das kantonale Gericht lediglich zu prüfen hatte, ob die IV-Stelle gestützt auf die ihr vorgelegten Unterlagen zu Recht auf die Neuanmeldung nicht eingetreten war (vgl. <ref-ruling> E. 5.2.5 S. 68 f.).
4.3. Was die geltend gemachte gesundheitliche Verschlechterung der Rücken- und Nackenproblematik betrifft, stellen die entsprechenden Ausführungen unzulässige appellatorische Kritik an der vorinstanzlichen Beweiswürdigung dar, die ausser Acht zu bleiben hat (<ref-law>; <ref-ruling> E. 10.1 S. 444 unten f. mit Hinweisen). Sodann hat das kantonale Gericht im Einzelnen begründet, weshalb der Beschwerdeführer keine relevante Veränderung glaubhaft vorbringen konnte. Es legte dar, dass weder ein am 8. Februar 2013 angefertigtes MRI noch der Bericht des Hausarztes Dr. med. B._ vom 13. Dezember 2013 und auch nicht der Bericht des Spitals C._ vom 24. März 2014 eine relevante Veränderung zu belegen vermögen. Gestützt auf die Beurteilung des Dr. med. D._, FMH für Orthopädische Chirurgie, vom 26. April 2013 sowie auf die RAD-Berichte vom 14. April und 1. Oktober 2015 erwog es, den degenerativen Veränderungen komme "wie bereits früher" keine wesentliche Bedeutung zu. Die zu diesem Schluss führende vorinstanzliche Sachverhaltswürdigung ist weder offensichtlich unrichtig noch sonstwie rechtsfehlerhaft und daher für das Bundesgericht verbindlich. Bei den gegebenen Umständen verletzt es auch nicht Bundesrecht, wenn das kantonale Gericht keinen Anlass zu weiteren Beweismassnahmen sah (vgl. E. 4.2 hievor). Der letztinstanzlich neu aufgelegte Bericht des Dr. med. B._ vom 26. April 2016 hat, da nicht durch den angefochtenen Entscheid veranlasst, als unzulässiges echtes Novum unbeachtlich zu bleiben (<ref-law>). Damit hat es bei dem vom kantonalen Gericht bestätigten Nichteintreten der IV-Stelle auf die Neuanmeldung vom 23. Februar 2015 sein Bewenden.
5.
Da die Beschwerde offensichtlich unbegründet ist (<ref-law>), wird sie im vereinfachten Verfahren mit summarischer Begründung und unter Hinweis auf den angefochtenen Entscheid (<ref-law>) erledigt.
6.
Die Gerichtskosten (<ref-law>) gehen ausgangsgemäss zu Lasten des Beschwerdeführers (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 23. Juni 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Huber