Sachverhalt: A. Das Betreibungsamt Wädenswil stellte der X._ AG in der gegen sie angehobenen Betreibung Nr. xxx am 11. Oktober 2012 die Konkursandrohung zu. Die Schuldnerin erhob am 22. Oktober 2012 betreibungsrechtliche Beschwerde und verlangte die Aufhebung der Konkursandrohung bzw. Feststellung der Nichtigkeit. Sie rügte, das Betreibungsamt sei zum Erlass der Verfügung örtlich nicht zuständig, da sie ihren statutarischen Sitz am 11. Oktober 2012 - am Tag der Zustellung der Konkursandrohung - nach Wollerau/SZ verlegt habe. Mit Urteil vom 3. Dezember 2012 wies das Bezirksgericht Horgen als untere Aufsichtsbehörde über Schuldbetreibung und Konkurs die Beschwerde ab. B. Die X._ AG gelangte an das Obergericht des Kantons Zürich, II. Zivilkammer, als obere kantonale Aufsichtsbehörde über Schuldbetreibung und Konkurs, welches die Beschwerde mit Urteil vom 4. Februar 2013 ebenfalls abwies. C. Mit Eingabe vom 18. Februar 2013 hat die X._ AG Beschwerde in Zivilsachen erhoben. Die Beschwerdeführerin verlangt die Aufhebung des Urteils der oberen kantonalen Aufsichtsbehörde vom 4. Februar 2013. In der Sache beantragt sie die Aufhebung der Konkursandrohung bzw. die Feststellung der Nichtigkeit; eventuell sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Weiter ersucht die Beschwerdeführerin um aufschiebende Wirkung. Mit Präsidialverfügung vom 5. April 2013 wurde der Beschwerde aufschiebende Wirkung zuerkannt. Das Betreibungsamt beantragt die Gutheissung (recte: Abweisung) der Beschwerde. Die obere kantonale Aufsichtsbehörde hat auf eine Stellungnahme verzichtet. Die Betreibungsgläubigerin (Beschwerdegegnerin) hat sich im bundesgerichtlichen Verfahren nicht vernehmen lassen.