After many years of extremely low success rates, a radical new design of the first semester arithmetic remedial course was implemented and studied. Students at a large urban community college could take a traditional semester-long traditional lecture-based remedial arithmetic course or a new accelerated 4-week 20-hour problem-solving based alternative remedial arithmetic course. Students taking the accelerated course passed a common exit exam at a statistically significant increased rate. However, those students did not pass the subsequent remedial algebra class at a statistically significant different rate, suggesting that, although the shorter problem-solving based class format improved student achievement in an individual class, more is required to sustain a lasting impact. The pedagogical and structural changes involved in this redesign are also discussed.