Increasing influence of Atlantic water in the Arctic Ocean has the potential to significantly impact regional water temperature and salinity. Here we use a rDNA barcoding approach to reveal how microbial communities are partitioned into distinct assemblages across a gradient of Atlantic-Polar Water influence in the Norwegian Sea. Data suggest that temperate adapted bacteria may replace cold water taxa under a future scenario of increasing Atlantic influence, but the eukaryote response is more complex. Some abundant eukaryotic cold water taxa could persist, while less abundant eukaryotic taxa may be replaced by warmer adapted temperate species. Furthermore, within lineages, different taxa display evidence of increased relative abundance in reaction to favourable conditions and we observed that rare microbial taxa are sample site rather than region specific. Our findings have significant implications for the vulnerability of polar associated community assemblages, which may change, impacting the ecosystem services they provide, under predicted increases of Atlantic mixing and warming within the Arctic region.