This study documents the time evolution of air temperature and heat waves occurrences over Northern Africa for the period 1979-2011. A significant warming (1°-3°C), appearing by the mid-1960s over Sahara and Sahel, is associated with higher/lesser frequency of warm/cold temperatures, as with longer duration and higher occurrences of heat waves. Heat waves episodes of at least 4 day duration have been examined after removing the long-term evolution. These episodes are associated with specific anomalies: (i) in spring, positive low-level temperature anomalies over the Sahel and Sahara; low and midlevel cyclonic rotation over Morocco associated with a Rossby wave pattern, lessening the Harmattan; more/less atmospheric moisture westward/eastward to 0°; upward/downward anomalies above the western/eastern regions associated with the Rossby wave pattern; (ii) in summer, a similar but weaker positive low-level temperature anomaly (up to 3°C); less moisture westward to 10°W, a cyclonic anomaly in central Sahel favoring the monsoon eastward to 0° and a midlevel anticyclonic anomaly over the Western Sahara, increasing southward the flux divergence associated with the African Easterly Jet. In March-May, two to three heat waves propagate eastward. They are preceded by an abnormal warm cell over Libya and southwesterlies over the West Sahara. A large trough stands over North Atlantic while midtropospheric subsidence and anticyclonic rotation reinforce over the continent, then migrates toward the Arabian peninsula in breaking up. These signals are spatially coherent and might suggest the role of short Rossby waves with an eastward group velocity and a baroclinic mode, possibly associated with jet stream deformation.