Debranched unacetylated and acetylated potato starches with two degrees of substitution, 0.041 (low) and 0.078 (high), combined with or without β-amylase hydrolysis were prepared to form soluble and insoluble complexes with stearic acid. The effects of modifications on the complexation, thermal properties, and X-ray patterns of soluble and insoluble complexes were investigated. Acetylation decreased the recovery of insoluble complexes but increased that of soluble complexes. Low acetylated, β-amylase-treated starch had a significantly increased amount of complexed stearic acid (123.1 mg/g) for insoluble complexes; high acetylated, β-amylase-treated starch had the highest complexed stearic acid (61.2 mg/g) for the soluble complexes. The melting temperature of the complexes decreased with acetylation. All β-amylase-treated acetylated complexes displayed the V-type diffraction pattern with peaks at 2θ = 7.4°, 12.9°, and 20°. These results suggest that starch can be modified by acetylation, debranching, and/or β-amylase to produce significant quantities of soluble starch-stearic acid complexes.