Accurately mapping the spatial distribution of forests in sub-humid to semi-arid regions over years is a challenging task and causes difficulty to forest management. Relatively large uncertainties still exist in the spatial distribution of forests and deforestation in the sub-humid and semi-arid regions. Numerous publications have used either optical or synthetic aperture radar (SAR) remote sensing imagery, but the resultant forest cover maps often have large errors. In this study, we proposed a pixel- and rule-based algorithm to identify and map annual forests from 2007 to 2010 in Oklahoma, USA, a transition region with various climate and landscapes, using the integration of the L-band ALOS PALSAR Fine Beam Dual Polarization (FBD) mosaic dataset and Landsat images. The overall accuracy and Kappa coefficient of the PALSAR/Landsat forest map were about 88.2% and 0.75 in 2010, with the user and producer accuracy about 93.4% and 75.7%, based on the 3,270 random ground plots collected in 2012 and 2013. Compared with the forest products from JAXA, NLCD, OKESM and OKFRA, the PALSAR/Landsat forest map showed great improvement. The area of the PALSAR/Landsat forest was about 40,149 km2 in 2010, which was close to the area from OKFRA (40,468 km2), but much larger than those from JAXA (32,403 km2) and NLCD (37,628 km2). We analyzed annual forest cover dynamics, and the results show extensive deforestation (2,761 km2, 6.9% of the total forest area in 2010) and reforestation (3,630 km2, 9.0%) in the southeast and central Oklahoma, and the total area of forests increased by 684 km2 from 2007 to 2010. This study clearly demonstrates the potential of data fusion between PALSAR and Landsat images for mapping annual forest cover dynamics in sub-humid to semi-arid regions, and the resultant forest maps would be helpful to forest management.