Sachverhalt: A. Der 1956 geborene türkische Staatsangehörige O._ reiste im Oktober 1989 in die Schweiz ein, wo er als Flüchtling anerkannt wurde. Von 1992 bis 1996 absolvierte er eine Ausbildung zum dipl. Sozialpädagogen. Diesen Beruf übte er vom 1. August 1996 bis 21. Februar 1999 in einem Pensum von 80 % aus. Im März 1999 meldete er sich bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Basel-Stadt sprach ihm Umschulung zum eidg. dipl. Fahrlehrer zu, die er erfolgreich absolvierte und ihm die Erzielung eines rentenausschliessenden Einkommens ermöglichte (Verfügung vom 9. Februar 2000). Im April 2008 ersuchte O._ um eine Invalidenrente. Nach Abklärungen und Durchführung des Vorbescheidverfahrens ermittelte die IV-Stelle einen Invaliditätsgrad von 20 % und verneinte mit Verfügung vom 6. März 2012 einen Rentenanspruch. B. Die dagegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 13. Mai 2013 gut, soweit es darauf eintrat. Es hob die Verfügung vom 6. März 2012 auf und sprach O._ ab 1. April 2007 eine ganze Invalidenrente zu. C. Die IV-Stelle beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, der Entscheid vom 13. Mai 2013 sei aufzuheben und die Angelegenheit sei zu weiteren medizinischen Abklärungen unter Neubeurteilung der Frage der Überwindbarkeit einer posttraumatischen Belastungsstörung an sie selber zurückzuweisen. Zudem ersucht sie um aufschiebende Wirkung der Beschwerde. O._ lässt auf Abweisung der Beschwerde schliessen, soweit darauf einzutreten sei; eventuell sei die Angelegenheit nicht an die IV-Stelle, sondern an die Vorinstanz zurückzuweisen. Ferner lässt er unentgeltliche Rechtspflege beantragen. Das kantonale Gericht beantragt die Abweisung des Rechtsmittels, das Bundesamt für Sozialversicherungen dessen Gutheissung. Dazu lässt O._ eine weitere Stellungnahme einreichen. 