Sachverhalt: A. Die 1949 geborene F._ ist kosovarische Staatsangehörige und wohnt in Kosovo. Nachdem ihr Ehemann G._, ebenfalls kosovarischer Staatsangehöriger, am 30. April 2011 in der Schweiz verstorben war und bis dahin eine Altersrente der Schweizerischen AHV bezogen hatte, meldete sie sich am 22. Juni 2011 (Eingang 23. August 2011) bei der Schweizerischen Ausgleichskasse (nachfolgend: SAK) zum Bezug einer Hinterlassenen-rente an. Die SAK berechnete eine mögliche Witwenrente, prüfte aber auch für einen allfälligen Anspruch auf Rückvergütung der Beiträge, in welcher Höhe bereits Rentenbetreffnisse an den Versicherten ausbezahlt worden waren, um zu entscheiden, ob F._ die Formulare für die Beitragsrückvergütung zugesandt werden sollten oder nicht, wovon die SAK schliesslich absah. Am 29. September 2011 verneinte die SAK verfügungsweise einen Anspruch auf eine Hinterlassenenenrente, da das zwischen der Schweiz und dem ehemaligen Jugoslawien abgeschlossene Sozialversicherungsabkommen ab 1. April 2010 im Verhältnis zu Kosovo nicht weiter angewendet werde. Daran hielt die SAK mit Einspracheentscheid vom 13. Juli 2012 fest. B. Das Bundesverwaltungsgericht hiess die dagegen erhobene Beschwerde gut, hob den Einspracheentscheid vom 13. Juli 2012 auf und sprach F._ eine monatliche Witwenrente von Fr. 1'290.- mit Wirkung ab 1. Mai 2011 zu (Entscheid vom 8. März 2013). In der Begründung führte es aus, dass das zwischen der Schweiz und dem ehemaligen Jugoslawien abgeschlossene Sozialversicherungsabkommen auf kosovarische Staatsangehörige weiter anwendbar sei. C. Die SAK erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt, der Entscheid des Bundesverwaltungsgerichts vom 8. März 2013 sei aufzuheben und ihr Einspracheentscheid vom 13. Juli 2012 zu bestätigen. F._ lässt auf Abweisung der Beschwerde schliessen und um Gewährung der unentgeltlichen Rechtspflege ersuchen. Das Bundesamt für Sozialversicherungen (BSV) stellt Antrag auf Gutheissung der Beschwerde. Das Bundesverwaltungsgericht verzichtet auf eine Vernehmlassung.