Перший професійний контракт Андрій підписав у 16 років з брестським«Динамо» і вже на другий рік свого перебування в команді став одним з основних захисників клубу. Його помітили тренери найсильнішого клубу країни, мінського«Динамо». Зумівши витримати сильну конкуренцію в оборонні клубу, Островський на кілька років став основним захисником команди, та 1994 року йому прийшло запрошення з національної збірної Білорусі. Незабаром Островському прийшла пропозиція з московського «Динамо», де в перший же сезон він разом з командою виграв бронзу чемпіонату Росії. Відігравши три сезони в «Динамо», Андрій переїхав до Ізраїлю, в якому за два роки перебування виграв два титули чемпіона країни разом з «Маккабі» з міста Хайфа. У 2002 році йому надійшла пропозиція від київського«Арсеналу», в якому він відіграв три сезони, з невеликою перервою, коли на початку 2004 року спробував знову повернутися до російської футбольної першості, підписавши контракт з клубом «Москва» з однойменного міста. Але там справи не склалися, і він повернувся назад до «Арсеналу». Останнім клубом кар'єрі Островського став одеський «Чорноморець». У 34 роки Андрій був змушений завершити кар'єру через травму тазостегнового суглоба, яку він так і не зміг вилікувати. Прощальний матч відбувся 7 жовтня2007 року в його рідному Пінську між місцевою командою «Волна» та командою «Друзів Островського».