Faits: A. Le 14 décembre 2012, X._ BV ( poursuivante ) a adressé à l'Office des poursuites de Genève une réquisition de poursuite dirigée contre A._ ( poursuivi ), en indiquant l'adresse suivante: «...». Le pli recommandé contenant cet envoi a été distribué à l'Office le 17 décembre suivant; celui-ci a enregistré la réquisition le 3 janvier 2013 ( n° xxxx ). Le commandement de payer a été notifié le 28 janvier 2013 en main de l'épouse du poursuivi, qui a formé opposition. Le 31 janvier 2013, le poursuivi a informé l'Office qu'il avait quitté la Suisse le 31 décembre 2012 pour s'établir en Turquie, où il vivait depuis le début de l'année, séparé de son épouse; à l'appui de ses dires, il a produit un formulaire d'annonce de départ déposé le 21 décembre 2012 auprès de l'Office cantonal de la population. B. Par décision du 4 février 2013, l'Office a annulé la notification du commandement de payer et déclaré « nulle et de nul effet » la poursuite n° xxxx; il a retenu que, vu l'absence de domicile du débiteur à B._, il était incompétent à raison du lieu. Statuant le 2 mai 2013, la Chambre de surveillance des Offices des poursuites et faillites de la Cour de justice du canton de Genève a déclaré irrecevable le chef de conclusions de la poursuivante tendant à la constatation de la validité de la réquisition de poursuite et rejeté la plainte au fond. C. Par acte du 16 mai 2013, la poursuivante forme un recours en matière civile au Tribunal fédéral; elle conclut principalement à l'annulation de la décision attaquée et, partant, à l'annulation de la décision de l'Office ainsi qu'à la constatation de la validité de la réquisition de poursuite et de l'invalidité du commandement de payer, subsidiairement à l'annulation de la décision attaquée et au renvoi de l'affaire à l'autorité précédente pour nouvelle décision. L'autorité précédente renonce à répondre; l'Office confirme sa décision et se réfère à son rapport explicatif; l'intimé propose le rejet du recours ainsi que la confirmation de la décision attaquée.