Early in the morning of February 20, Brig. Gen. Truman Seymour's army left Barbers' Station and moved westward towards Lake City. Because of the necessity of posting garrisons at Jacksonville and elsewhere, the Union force consisted of between 5,000 and 5,500 men. The small army was divided into three brigades of infantry, one brigade of mounted troops, and an artillery support unit.
The Federals advanced in 3 columns along the Lake City and Jacksonville Road, which ran roughly parallel to the Florida Atlantic and Gulf-Central Railroad. The Union cavalry was in the vanguard, followed by the slower-moving infantry. By mid-day, the Federals had reached Sanderson.
In the early afternoon of February 20, a few miles west of Sanderson, the advance elements of the Union cavalry engaged a few Confederates that appeared to their front. This skirmishing was maintained for several miles, with the Federals driving the Confederates westward towards the railroad station at Olustee. Confederate resistance intensified as the Federals neared Olustee.
After the fight at Lake City on February 11, Brig. Gen. Joseph Finegan moved his troops to Olustee Station. There, the Confederates found one of the few defensible locations in the area where the railroad passed through a narrow corridor for dry ground that was bordered by impassable swamps and bays to the south and a large body of water to the north. The Confederates built strong earthworks and waited for the Union advance.