Sachverhalt: A. Das Statthalteramt des Bezirks Bülach verurteilte X._ mit Strafbefehl vom 18. Juni 2012 wegen SVG-Widerhandlungen zu einer Busse von Fr. 400.--. X._ erhob dagegen am 28. Juni 2012 fristgerecht Einsprache. Das Statthalteramt stellte Busse und Kosten des Zahlungsbefehls am 18. Juni 2012 in Rechnung. Es liess X._ am 22. August 2012 eine Zahlungserinnerung zukommen und forderte ihn auf, den ausstehenden Betrag innert zehn Tagen zu bezahlen. Nach Ablauf dieser Frist werde die Betreibung eingeleitet bzw. der Vollzug der festgesetzten Ersatzfreiheitsstrafe von vier Tagen verfügt. X._ bezahlte die Rechnung am 10. September 2012. Gleichentags mandatierte er seine Rechtsvertreterin, welche am 12. September 2012 die Akten anforderte und sich am 1. Oktober 2012 beim Statthalteramt des Bezirks Bülach über den bisherigen Gang des Einspracheverfahrens beschwerte. B. Das Statthalteramt des Bezirks Bülach behandelte die Eingabe des Beschwerdeführers als Gesuch um Wiederherstellung der Einsprachefrist und gab diesem am 8. Oktober 2012 nicht statt. Das Obergericht des Kantons Zürich qualifizierte den Entscheid des Statthalteramts als Abschreibung des Strafbefehlsverfahrens und wies die vom Beschwerdeführer erhobene Beschwerde am 27. Februar 2013 ab. C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, die angefochtene Verfügung sei aufzuheben, das Statthalteramt sei anzuweisen, die Einsprache gegen den Strafbefehl materiell zu behandeln, die Kosten des kantonalen Verfahrens seien dem Kanton Zürich aufzuerlegen und es sei ihm dafür eine Entschädigung von Fr. 1'620.-- zuzusprechen. Eventuell sei die Sache zu neuer Entscheidung an das Obergericht des Kantons Zürich zurückzuweisen. Das Statthalteramt des Bezirks Bülach und die Vorinstanz verzichteten auf eine Stellungnahme. 