Po trzech sezonach spędzonych w IV lidze lubuskiej w sezonie 2002/2003 klub wywalczył awans po raz drugi w historii do III ligi. Jednak przez pierwsze trzy sezony klub nie radził sobie najlepiej unikając spadku tylko dzięki problemom innych klubów. W sezonie 2006/2007 Polonia powtórzyła pozycję z sezonu 1997/1998 zajmując ponownie czwarte miejsce w III lidze aczkolwiek tracąc do lidera 14 pkt., zdobywając mniej punktów i mając gorszy bilans bramkowy niż przed dziewięcioma sezonami. Kolejny sezon 2007/2008 klub zakończył na 6 pozycji dzięki czemu zapewnił sobie miejsce w reformowanej III lidze, która od następnego sezonu nazywała się II liga i liczbę grup zmniejszono z czterech do dwóch. W następnym sezonie 2008/2009 już II ligi drużyna zajęła ostatnie 16 miejsce jednak znów unikając spadku dzięki wycofaniu się z rozgrywek innych klubów. W tym samym sezonie drużyna rezerw grająca w A-klasie wywalczyła awans do klasy okręgowej. W sezonie 2009/2010 klub w rozgrywkach centralnych Pucharu Polski uzyskał najlepszy wynik w historii dochodząc do 1/16 finału gdzie przegrał dopiero z ekstraklasowym Piastem Gliwice. W tym samym czasie w lidze klub zajął 12. miejsce. thumb|left|Mecz II ligi zachodniej 2010/11: Polonia Słubice – Raków Częstochowa 25 stycznia 2011 r.