Sachverhalt: A. Die Familienausgleichskasse Arbeitgeber Basel (nachfolgend: FAK) richtete A._ bis und mit Juli 2015 Ausbildungszulagen für seine 1996 geborene Tochter B._ aus. Diese hatte vom 1. August 2014 bis 31. Juli 2015 in der Kindertagesstätte C._ ein Praktikum als Fachfrau Betreuung Kind absolviert. Da die Kindertagesstätte C._ per 30. Juni 2016 geschlossen wurde, konnte sie die dortige Lehrstelle nicht antreten. In der Folge verpflichtete sich B._ im Hinblick auf eine andere Lehrstelle zu einem weiteren Praktikum für die Dauer vom 17. August 2015 bis 12. August 2016 im Tagesheim D._. Mit Verfügung vom 17. September 2015 verneinte die FAK einen Anspruch auf Ausbildungszulagen ab 1. August 2015, da das zweite Praktikum nicht mehr als Ausbildung anerkannt werden könne. An ihrem Standpunkt hielt sie mit Einspracheentscheid vom 9. Oktober 2015 fest. B. Die hiegegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 22. Februar 2016 gut, hob den Einspracheentscheid vom 9. Oktober 2015 auf und wies die FAK an, A._ rückwirkend ab 17. August 2015 Ausbildungszulagen auszurichten. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die FAK die Aufhebung des kantonalen Gerichtsentscheids. A._ lässt auf Abweisung der Beschwerde schliessen. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.