Long-term changes of extratropical cyclone trajectories in the North Atlantic in cold months (October–March) were analyzed, with the data of Mean Sea Level Pressure archives from Climatic Research Unit, UK (1873–2000) and NCEP/DOE AMIP-II Reanalysis (1979–2021) being used. It was revealed that variations of latitudes of storm tracks in the longitudinal range from 60°W to 10°W are characterized by pronounced periodicities of ~80–90 and ~22 years. This indicates their possible relation to the corresponding periodicities in solar/geomagnetic activity and galactic cosmic ray variations, the secular Gleissberg cycle and the magnetic Hale cycle, respectively. At the maximum of the secular cycle, trajectories of North Atlantic cyclones were found to shift a few degrees south, whereas at the minimum and the descending phase they shift to the north. As North Atlantic cyclones influence significantly weather and climate conditions over Europe, oscillations of their tracks associated with solar activity and related phenomena seem to be of great prognostic importance.