The widespread promotion of conservation agriculture (CA) in regions with weathered soils prone to phosphorus (P) deficiency merits explicit consideration of its effect on P availability. A long-term CA field trial located on an acid, weathered soil in western Kenya was evaluated for effects of reduced tillage and residue retention on P availability. Reduced tillage and residues were hypothesized to increase soil aggregation, and as a result, reduce P sorption potential, increase labile and organic P (Po), and stimulate phosphatase activities. After 9 years (18 cropping seasons), residue management had no effect on soil aggregate mean weight diameter (MWD), soil P fractions, or phosphatase potential activities. However, reduced tillage increased soil MWD and labile soil P stocks at 0–15 cm depth. Total P was greater at 0–15 cm depth under reduced tillage, but not for 0–30 cm depth, indicating stratification of P under reduced tillage. Increases in total P at 0–15 cm depth were correlated with maximum P sorption (Pmax sorption), whereas labile P increased with MWD and Po stocks. Reduced tillage also decreased pH and increased Pmax sorption, but these properties were not correlated. Despite a positive association of MWD and Po, weak or no changes were observed for Po and phosphatase activities, nor were there management effects on soil C stocks. Low residue retention rates (2 t maize residue yr−1) and relatively small improvements in soil structure due to reduced tillage were likely insufficient to yield changes in Po. Fertilizer P inputs at recommended rates (60 kg P ha−1 per season) may have also muted treatment effects on organic P cycling, though phosphatase activities were positively correlated with inorganic P fractions. The reduced tillage component of CA offers some improvements in P availability in weathered soils of western Kenya. However, relatively low soil available P across treatments suggests that CA with P fertilization may not be an optimal P management strategy for weathered soils in this region.