1250, Portugal conquered the Algarve. Now that the South was secured, in 1256 Portugal's capital moved to Lissabon. In the year 1340, Portugal defeated the Moorish army together with Castille; this was the last time an Arab army landed on Iberian soil. During the years 1350-75, Portugal (like other countries) extended fishery in the North Atlantic, going farther and farther west. Soon, tales of strange islands in the far west started to spread among fishermen and sailors. 1355, Portuguese king Fernando I was deposed because of unspeakable cruelty, and his younger brother Diniz II took the power.