Sachverhalt: A. X._ (Ehemann, geb. 1964) und Z._ (Ehefrau, geb. 1966) wurden mit Scheidungsurteil des Bezirksgerichts Hinwil vom 4. März 2010 geschieden. Ihre Söhne S._ (geb. 1996), T._ und U._ (beide geb. 1998) wurden unter die elterliche Sorge der Mutter gestellt und der Vater wurde verpflichtet, Unterhaltsbeiträge von Fr. 900.-- bzw. ab 1. September 2012 Fr. 1'100.-- pro Kind und Monat zu bezahlen. B. Mit Eingabe vom 31. August 2012 leitete X._ ein Verfahren auf Abänderung des Scheidungsurteils ein. Er beantragte, die Unterhaltsbeiträge seien auf Fr. 650.-- pro Kind herabzusetzen. Anlässlich der Gerichtsverhandlung vom 6. November 2012 schlossen die Parteien eine Vereinbarung, worin er sich verpflichtete, Fr. 900.-- pro Kind zu leisten. Noch am selben Tag widerrief er die Vereinbarung schriftlich. Mit Urteil vom 22. November 2012 genehmigte das Bezirksgericht die Vereinbarung dennoch und schrieb das Verfahren als durch Vergleich erledigt ab. C. Am 28. Dezember 2012 reichte X._ hiergegen Berufung beim Obergericht des Kantons Zürich ein. Er verlangte eine Neufestsetzung der Unterhaltsbeiträge für die Kinder und des nachehelichen Unterhalts. Bezüglich der Vereinbarung vom 6. November 2012 machte er geltend, diese sei unrealistisch und könne aufgrund von Willensmängeln nicht aufrecht erhalten werden. Mit Entscheid vom 13. März 2013 trat das Obergericht wegen verspäteter Leistung des Kostenvorschusses von Fr. 4'000.-- auf die Berufung nicht ein. D. Gegen diesen Entscheid ist X._ (Beschwerdeführer) am 21. April 2013 an das Bundesgericht gelangt. Er beantragt in der Hauptsache die Aufhebung des Nichteintretensbeschlusses des Obergerichts; dieses habe auf seine Berufung einzutreten. Mit Eingabe vom 6. Juni 2013 übermittelte die Vorinstanz einen Auszug des Gerichtskontos. Danach ist die Zahlung des Beschwerdeführers am 26. Februar 2013 eingegangen. In der Sache liess sich das Obergericht nicht vernehmen. Die Beschwerdegegnerin teilte am 24. Juni 2013 mit, dass sie auf einen Antrag verzichte.