See Shofetim 3:13 where Eglon and Amalek attack Israel. In Shofteim 7:12 we see Amalek helping Midian. In Shofetim 10:12 G-d mentions how He saved the jews from Amalek.
Why didn’t the jews make a concerted attempt to destroy Amalek before king Shaul?
See Rambam Hilchos Melachim 1-2, that the Jews needed a king before they could wipe out Amalek.