w meczu przeciw Rumunii w Bukareszcie Ałeksandar Wasoski zdobył (główką po rzucie różnym) swego pierwszego gola w reprezentacji. To spotkanie Macedonia przegrała jednak 1-2. Runda jesienna sezonu 2004/2005 była jedną z najlepszych dla 25-letniego wówczas obrońcy. Zdobył 7 goli i grał bardzo pewnie w obronie, co zaowocowało w przerwie zimowej ofertą transferu do niemieckiego Eintrachtu Frankfurt – Wasoski odszedł do Niemiec za 200.000 euro, z czego 40% Vardar oddał na mocy klauzuli we wcześniejszej umowie Cementarnicy Skopje, lokalnemu rywalowi i poprzedniemu pracodawcy Wasoskiego.
Macedończyk dołączył w niemieckim klubie do swego rodaka, bramkarza Oki Nikołowa. W rundzie wiosennej sezonu 2004/2005 Wasoski pojawiał się już na boiskach 2. Bundesligi dosyć często, a jego zespół zajął 3. miejsce w tabeli i awansował do 1. Bundesligi. W sezonie 2005/2006 był już pewniakiem w defensywie beniaminka, który ostatecznie zajął 14. miejsce w tabeli, ale dzięki grze w finale Pucharu Niemiec zapewnił sobie grę w Pucharze UEFA 2006/2007.