Sachverhalt: A. Mit Zahlungsbefehl Nr. yyy des Betreibungsamtes Zürich 2 vom 10. November 2014 betrieb die B._ AG A._ über Fr. 4'893'413.80. A._ erhob Rechtsvorschlag. Am 16. Dezember 2014 ersuchte die B._ AG das Bezirksgericht Zürich um Rechtsöffnung. Das Bezirksgericht erteilte am 15. Mai 2015 definitive Rechtsöffnung für Fr. 4'891'974.55 und provisorische Rechtsöffnung für Fr. 1'439.25. Den Antrag von A._ auf Löschung der Betreibung wies das Bezirksgericht ab. B. Am 12. Juni 2015 erhob A._ Beschwerde an das Obergericht des Kantons Zürich. Er verlangte, das Urteil des Bezirksgerichts vom 15. Mai 2015 aufzuheben und das Rechtsöffnungsgesuch abzuweisen. Zudem ersuchte er um aufschiebende Wirkung. Das Obergericht wies das Gesuch um aufschiebende Wirkung am 14. September 2015 ab (vgl. dazu Verfügung 5A_741/2015 vom 18. April 2016). Mit Urteil vom 24. Februar 2016 wies das Obergericht die Beschwerde ab, soweit es darauf eintrat. C. Am 18. April 2016 hat A._ (Beschwerdeführer) Beschwerde in Zivilsachen an das Bundesgericht erhoben. Er verlangt die Aufhebung des Urteils des Obergerichts vom 24. Februar 2016 und die Abweisung des Rechtsöffnungsgesuchs. Am 21. April 2016 hat die B._ AG (Beschwerdegegnerin) beantragt, den Beschwerdeführer zur Sicherstellung der Parteientschädigung in angemessener Höhe, mindestens aber Fr. 20'000.--, zu verpflichten. Der Beschwerdeführer hat die Abweisung des Gesuchs beantragt. Mit Präsidialverfügung vom 9. Mai 2016 hat das Bundesgericht das Gesuch abgewiesen, da die Beschwerdegegnerin noch nicht zu einer Vernehmlassung aufgefordert worden war. Das Bundesgericht hat die Akten beigezogen, in der Sache aber keine Vernehmlassungen eingeholt.